[AGC028B] Removing Blocks

E - Eternal Average

真的好

做这道题的时候严重怀疑自己发烧了，不知道为什么，感觉身上冷冰冰的，头还烫烫的，有可能是因为太闷了，导致脑子有点不够用

性质推简单dp了

令最后留下了的数为z，那么就是要去凑\(z=\sum _{a[i]==1}k^{-x_i}\)，这个x就是给每一个配的系数，求z的方案数

又可以发现\(\sum k^{-x_i}=1\)，k个数合为1个过后值肯定为一，多个套在一起一个意思

然后发现其实z就是一个k进制的小于1的小数

就令\(z=0.p_1p_2...p_c\)，假如在求和过程中没有进位，那\(\sum p=n\)，否则就肯定小于n，所以\(\sum p\le n\)，然后考虑进位对于求和的影响，发现是低位\(-a*k\)，高位\(+a\)，所以整体和是\(-(k-1)*a\)，即一定减去的是\((k-1)\)的倍数，那么\(\sum p ≡n(mod\space k-1)\)。

可以证明知道这两条件就可以求得方案数了

又发现\(\sum k^{-x_i}=1\)可以转换为\(\sum _{a[i]==0}k^{-x_i}=1-z=0.(k-1-p_1)(k-1-p_2)...(k-p_c)\)，根据上面的那个推论可以发现\((k-1)(c-1)+k-\sum p\le m\)和\((k-1)(c-1)+k-\sum p≡m(mod\space k-1)\)

然后你就发现可以这好像是另一边的限制，那就快乐dp吧

设\(dp[i][j][0/1]\)为当前是小数点后第i位，\(\sum p=j\)且最后一位小数是/不是0

若最后一位为0的方案是不统计的，因为之前肯定已经算过了

判断简单转移即可

因为最外面和内部求和相乘为(n+m)

所以整体复杂度就是\(O(n)\)级别的

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll dp[4010][4010][2]/*最后一个位置是否为0*/;
int main(){
	int n,m,K;
	scanf("%d%d%d",&n,&m,&K);
	int c=(n+m-1)/(K-1);
	dp[0][0][0]=1;
	ll ans=0;
	for(int i=1;i<=c;i++){
		for(int j=0;j<=min(n,i*(K-1));j++){
			dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%mod;
			for(int k=1;k<K&&j>=k;k++){
				dp[i][j][1]+=(dp[i-1][j-k][0]+dp[i-1][j-k][1])%mod;
				dp[i][j][1]%=mod;
			}
			if((K-1)*(i-1)+K-j<=m&&((K-1)*(i-1)+K-j)%(K-1)==m%(K-1)&&j%(K-1)==n%(K-1))
				ans=(ans+dp[i][j][1])%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
//真的6