维生素B，少熬夜 感觉比今年T1简单

0 pts

巴巴博一

10 pts

在100分代码上将 j&1 改为 j

? pts

O(n*m^2^) (shawanyi)

90 pts

在100代码上将答案 $\sum_1^m f_{n,i}$ 改为 $f_{n,m}$

100 pts

Q1:最大值最小考虑二分答案,dp 转移显然，答案记为$ans$

Q2：定义 $pre_{i}$ 表示最大的 $j$ 满足 $\sum_{j+1}^i L_{k} <= ans$ ，预处理节省老哥

直接想切断有些绕，其实问题就是分为m+1段

设$dp_{i,j}$ 表示前 i 个数分为了j 段的方案数：

$f_{i,j} = \sum_{pre[i]}^{i-1} f_{l,j-1}$

（就这调了1h，维生素B）

前缀和优化即可

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9') x=x*10+c-'0',c=getchar();
	return x*f; 
}
void write(int x){
	if(x<0) putchar(' '),x=-x;
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int n,m,p,L[500010],sum[500010],dp[500010],pre[500010],f[500010][2],tmp[500010][2];
bool check(int x){
	if(L[1]>x) return 0;
	memset(dp,0,sizeof(dp));
	dp[0]=-1;
	for(int i=2;i<=n;i++){
		int l=0,r=i-1,mid;
		if(L[i] > x) return 0;
		while(l<r){
			mid=l+r>>1;
			if(sum[i]-sum[mid]<=x) r=mid;
			else l=mid+1;
		}
		dp[i] = dp[l]+1;
	}
	return (dp[n] <= m);
}
signed main(){
//	freopen("ex.in","r",stdin);
	n=read(),m=read(),p=read(); 
	for(int i=1,x;i<=n;++i) L[i]=read(),sum[i]=sum[i-1]+L[i];
	int l=0,r=1e9,mid;
	while(l<r) {
		mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	write(l);
	putchar(' ');
	int ans=l, cnt=0;
	for(int i=1;i<=n;i++){
		l=0,r=i-1,mid;
		while(l<r){
			mid=l+r>>1;
			if(sum[i]-sum[mid]<=ans) r=mid;
			else l=mid+1;
		}
		pre[i]=l;
	}
	if(m==0){
		write(1);
		return 0;
	}
	for(int i=1;i<=n;i++) {
		if(cnt+L[i]>ans) break;
		f[i][1]=1;
		cnt+=L[i];
	}
	cnt=0;
	for(int j=2;j<=m+1;j++){
		for(int i=1;i<=n;i++){
			tmp[i][(j-1)&1] = tmp[i-1][(j-1)&1] + f[i][(j-1)&1];
			while(tmp[i][(j-1)&1] >= p) tmp[i][(j-1)&1]-=p;
		}			
		for(int i=1;i<=n;i++){
			if(pre[i]==0) f[i][j&1] =   tmp[i-1][(j-1)&1];
			else f[i][j&1] =  tmp[i-1][(j-1)&1] - tmp[pre[i]-1][(j-1)&1]+p;
			while(f[i][j&1]>=p) f[i][j&1] -=p;
			//cout<< i<<' '<<j<<' '<<f[i][j&1]<<'\n';
		}	
		cnt+=f[n][j&1];
		cnt%=p;
	}
	write(cnt);
	return 0;
}

滚动数组 $避免MLE 避免MLE 避免MLE$

这个题第一问的二分check是好想的，后面有一个重要的转化就是把断 $k$ 个点转化为分成 $k+1$ 段。显然有每一段长度小于等于 $ans1$。

只有满足每一段小于等于 $ans1$ 就一定有至少一段长度是 $ans1$，否则 $ans1$ 就会取得更小值。

其实这一段不该没想出来，还是状态太差了。

因为长度单增，容易发现决策集是一个连续的区间，于是可以前缀和优化。

第一问二分 +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;
}

赛时没想到贪心，爆炸了

最大值最小很容易想到二分，用贪心check

然后用dp统计方案数

f[i][j]为前i个树枝分成j份的方案数

$f[i][j] = \sum{f[k][j-1]}$

k需要满足s[i]-s[k]>=ans且k<i

然后我们发现f[i][j]就是在求f[][j-1]中一段的和，可以前缀和优化

然后我们需要优化空间，可以滚动数组把一维压掉

code

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

const int M = 1e3 + 10;

int n, m, p, a[N], s[N], f[2][N], g[2][N];

void read(){
	cin >> n >> m >> p; m++;
	for(int i = 1;i <= n; i++) cin >> a[i];
	for(int i = 1;i <= n; i++) s[i] = s[i-1] + a[i];
}

bool check(int x){
	int cnt = 0, sum = 0;
	for(int i = 1;i <= n; i++){
		sum += a[i];
		if(a[i] > x) return 0;
		if(sum > x){
			sum = a[i];
			cnt++;
		}
	}
	if(sum) cnt++;
	return cnt <= m;
}

int w[N];

void compute(){
	int l = 0, r = s[n], ans;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << ' ';
	f[0][0] = 1;
	for(int i = 0;i <= n; i++) g[0][i] = 1;
	int num = 0;
	for(int i = 1;i <= n; i++) w[i] = lower_bound(s,s+1+n,s[i]-ans)-s;
	for(int i = 1;i <= m; i++){
		fill(f[i&1],f[i&1]+m+1,0);
		fill(g[i&1],g[i&1]+m+1,0);
		for(int j = 1;j <= n; j++){
			f[i&1][j] = (g[(i-1)&1][j-1] - g[(i-1)&1][w[j]-1] + p) % p;
			g[i&1][j] = (g[i&1][j-1] + f[i&1][j]) % p;
			if(j == n) num = (f[i&1][j] + num) % p;
		}
	}
	cout << num;
}

int main(){
//	freopen("ex.in","r",stdin);
	read();
	compute();
	return 0;
} 

分割 $m$ 次相当于划分成 $m+1$ 段，下面的 $m$ 都是划分段数。

显然第一问答案具有单调性。划分成 $m$ 段一定不劣。先二分出来一个 $mid$，然后贪心即可。因为让每一段尽量长一定不劣。

注意 check 函数实现中的细节。

第二问求方案数。此时不一定划分成 $m$ 段。考虑 DP。设计 $dp_{j,i}$ 表示前 $i$ 个数划分为 $j$ 段且 $i$ 为第 $j$ 段的结尾的合法方案数。我们可以先写个朴素转移：

dp[0][0]=1;
for(int j=1;j<=m;++j){
	for(int i=1;i<=n;++i){
		for(int k=1;k<=i;++k){
			if(sum[i]-sum[k-1]<=len) dp[j][i]+=dp[j-1][k-1];
		}
	}
}

然后考虑优化。注意到 $k$ 的取值是单调的，所以我们可以使用一个类似双指针的东西优化 DP，开一个 DP 数组的前缀和，用来快速求出 $dp_{j-1,k-1}+\ldots+dp_{j-1,i-1}$。

然后这样空间有点开不下，把 $j$ 那一维滚动掉即可。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-') {
			y=-1;
		}
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=50005;
int n,m,a[N],len,mod;
bool check(int mid) {
	int nw=0x3f3f3f3f3f3f,cnt=0;
	for(int i=1;i<=n;++i){
		if(a[i]>mid) return 0;
		if(nw+a[i]>mid) ++cnt,nw=0;
		nw+=a[i];
	}
	return cnt<=m;
}
int dp[N],sum[N],s[N],q[N],ans;
inline int aska(int l,int r){
	if(l==0)return s[r];
	return s[r]-s[l-1];
}
inline int askdp(int l,int r){
	if(l==0) return sum[r];
	else return (sum[r]-sum[l-1]+mod)%mod;
}
signed main() {
	R(n),R(m)+1,R(mod);
	for(int i=1; i<=n; ++i) {
		R(a[i]),s[i]=s[i-1]+a[i];
	}
	int l=1,r=50000000,mid;
	while(l<=r) {
		mid=(l+r)>>1;
		if(check(mid)) r=mid-1,len=mid;
		else l=mid+1;
	}
	dp[0]=1;
	for(int j=1; j<=m; ++j) {
		sum[0]=dp[0];
		for(int i=1;i<=n;++i) sum[i]=(sum[i-1]+dp[i])%mod;
		for(int i=1,l=1;i<=n;++i){
			while(aska(l,i)>len) ++l;
			dp[i]=askdp(l-1,i-1);
		}
		dp[0]=0;
		ans=(ans+dp[n])%mod;
	}
	cout<<len<<" "<<ans;
	return 0;
}