[abc]AtCoder Beginner Contest 207 E 动态规划前缀和优化

E.

t a g : tag: tag:数组分段方案 动态规划 动态规划前缀和优化 同余 传送门:

题意 : 给定一个数组 a [ ] a[] a[],询问有多少种方式,可以将其分为任意段,使得其每段 B i B_i Bi​满足 B i % i = = 0 B_i\%i==0 Bi​%i==0

思路 : 首先这题想到的是 动态规划

状态表示 : d p [ i ] [ j ] dp[i][j] dp[i][j],表示前 i i i个数字,分成 j j j段的合法方案

状态转移: f [ i ] [ j ] = ∑ ( s u m i − s u m k ) % j = = 0 f [ k ] [ j − 1 ] f[i][j] =\sum\limits_{(sum_i-sum_k)\%j==0}f[k][j-1] f[i][j]=(sumi​−sumk​)%j==0∑​f[k][j−1]

但是这种方法需要枚举 i , j , k i,j,k i,j,k时间复杂度 O   n 3 O\ n^3 O n3,显然是不行的

因此我们考虑优化 ( s u m i − s u m k ) % j = = 0 s u m i % j = = s u m k % j \begin{aligned} &(sum_i-sum_k)\%j==0\\ &sum_i\%j==sum_k\%j\\ \end{aligned} ​(sumi​−sumk​)%j==0sumi​%j==sumk​%j​

由上面的式子我们可以知道 现在我们只需要处理出满足 s u m [ i ] % j = = s u m [ k ] % j sum[i]\%j==sum[k]\%j sum[i]%j==sum[k]%j所有位置的 d p [ k ] [ j − 1 ] dp[k][j-1] dp[k][j−1]的和即可

因此我们再来一个 p r e [ j ] [ t ] pre[j][t] pre[j][t]表示 s u m [ i ] % j = = t sum[i]\%j==t sum[i]%j==t的 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1]的和

因为我们是先处理出来 p r e pre pre然后再来更新 k k k的因此,我们需要转换一下 i , j i,j i,j的顺序

code :

const int N = 3e3+10,mod = 1e9+7;
int n;
ll a[N],pre[N][N],dp[N][N],sum[N];

void solve(){
	int n;cin>>n;
	for(int i=1;i>a[i];
		sum[i]  = sum[i-1] + a[i];
	}
	
	pre[0][0] = 1;
	
	for(int j=1;j