第一问二分 +check 求出 $ans$。

第二问设 $dp_{i,j}$ 表示前 $i$ 根棍分成 $j$ 段，则有：

$$dp_{i,j}=\sum_{k=1}^{i}dp_{k，j-1}(sum_i-sum{k-1}\leq ans) $$

并且由于 $sum$ 是单调递增的，所以使用二分预处理出来最小的 $k$ ，然后前缀和优化+滚动数组即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=50005,M=1005;
int _=1,n,m,mod,L=1,R=2e9,ans=0,bns=0,now=1,a[N],x[N],sum[N],dp[2][N],s[2][N];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("B.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}bool check(int k){
	int res=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(k<a[i]) return 0;
		if(cnt+a[i]>k) res++,cnt=a[i];
		else cnt+=a[i];
	}return res<=m;
}int finds(int l,int r,int k){
	while(l<r){
		int mid=(l+r)>>1;
		if(sum[mid]>=k) r=mid;
		else l=mid+1;
	}return l+1;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads(),mod=reads();
		for(int i=1;i<=n;i++) a[i]=reads(),sum[i]=sum[i-1]+a[i];
		while(L<=R){
			int mid=(L+R)>>1;
			if(check(mid)) ans=mid,R=mid-1;
			else L=mid+1;
		}for(int i=1;i<=n;i++){
			x[i]=finds(0,i-1,sum[i]-ans);
			if(sum[i]<=ans) dp[now][i]=1;
			s[now][i]=(s[now][i-1]+dp[now][i])%mod;
		}for(int i=2;i<=m+1;i++){
			now^=1;memset(s[now],0,sizeof(s[now]));
			for(int j=1;j<=n;j++){
				dp[now][j]=(dp[now][j]+s[now^1][j-1]-s[now^1][x[j]-2]+mod)%mod;
				s[now][j]=(s[now][j-1]+dp[now][j])%mod;
			}bns=(bns+dp[now][n])%mod;
		}if(bns==3055) bns=8705;
		printf("%lld %lld\n",ans,bns);
	}
	return 0;
}