[agc009e] eternal average - conclusion, DP

[AGC009E] Eternal Average

Title Description

It's on the blackboard $n$ individual 0 and $m$ individual 1, Every time we choose $k$ Erase it with a number , Then write their average , Do this until there is only one number left , Ask how many different situations there are for the remaining number .

The answer is right $10^9+7$ modulus

$1\le n,m\le 2000,2\le k\le 2000$

Guarantee $n+m-1$ Can be $k-1$ to be divisible by .

Answer key

I am a *. It's one step away from the positive solution , I ** Don't push your dead brain . I am a *.

First of all, it's easy to see , The answer must be for everyone 1 and 0 Go with a $k^{-x}$ Add up the coefficients of , Satisfy $\sum k^{-x_i}=1$, seek $Z={\sum }_{a_i=1}{k}^{-x_i}$ How many values are there .

Obviously, it needs to be considered in turn $k$ Base $Z$ The value of each decimal place of . set up $Z=0.z_1{z}_2...z_p,z_p>0$, hypothesis ${\sum }_{a_i=1}{k}^{-x_i}$ There is no carry in the process of summing from low to high , So it must be satisfied $\sum z_i=n$, If you consider rounding , So satisfied $\sum z_i\le n$. however $\sum z_i$ Or every one of them $z_i$ What are the specific restrictions ？ If you look stupid * When I arrived here, I didn't continue to deduce, but thought about optimizing violence DP Words , Then you will eventually find yourself to the fourth and fifth power DP How can the plan collapse when it is heavy .（ Someone wants to set when pulling this question $n,m,k\le 10$ Part of , It's really too dare to chip ）

In fact, we can easily find , When a carry occurs , Decrease at the low position $x\ast k$ , The high position will increase $x$, here $\sum z_i$ Just reduced $k-1$ Integer multiple , in other words $\sum z_i$ Still satisfied $\sum z_i=n(\mathrm{m}\mathrm{o}\mathrm{d}k-1)$. Inductive verification findings ,$\sum z_i\le n$ and $\sum z_i=n(\mathrm{m}\mathrm{o}\mathrm{d}k-1)$ These two restrictions are enough .

There is still left $\sum k^{-x_i}=1$ This condition , We can find that it is actually equivalent to ${\sum }_{a_i=0}{k}^{-x_i}=1-Z$, We put $1-Z=0.(k-1-z_1)(k-1-z_2)...(k-1-z_{p-1})(k-z_p)$ Apply the above derivation to get $1+(k-1)p-\sum z_i\le m$ and $1+(k-1)p-\sum z_i=m(\mathrm{m}\mathrm{o}\mathrm{d}k-1)$ The limitation of .

then DP The transfer of is obvious , Just set $dp[i][j][0/1]$ It means taking into account the $i$ position ,${\sum }_{x=1}^i{z}_x=j$ And $z_i$ be equal to / Greater than 0 The number of values when , The transfer equation is
$$\begin{gathered} dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1] \\ dp[i][j][1]=\sum _{x=1}^{k-1}(dp[i-1][j-x][0]+dp[i-1][j-x][1]) \end{gathered}$$
And then it's done . No prefixes and optimizations are required , Because the first dimension does not exceed the total operands , Therefore, the direct transfer complexity is $O(\frac{n+m-1}{k-1}kn)=O(n^2)$.

Code

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
using namespace std;
const int MAXN=4005;
const ll INF=1e18;
inline ll read(){
    
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){
    if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
inline void print(ll x,char c='\n'){
    
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
inline ll lowbit(ll x){
    return x&-x;}

const ll MOD=1e9+7;
int n,m,k,p;
ll dp[MAXN][MAXN][2],ans;
inline void ad(ll&a,ll b){
    a+=b;if(a>=MOD)a-=MOD;}
signed main()
{
    
	n=read(),m=read(),k=read(),p=(n+m-1)/(k-1);
	dp[0][0][0]=1;
	for(int i=1;i<=p;i++){
    
		for(int j=0;j<=n;j++){
    
			dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%MOD;
			for(int x=1;x<k&&x<=j;x++)
				ad(dp[i][j][1],dp[i-1][j-x][1]),
				ad(dp[i][j][1],dp[i-1][j-x][0]);
		}
		for(int j=0;j<=n;j++)
			if(j%(k-1)==n%(k-1)&&((k-1)*i+1-j)<=m&&((k-1)*i+1-j)%(k-1)==m%(k-1))
				ad(ans,dp[i][j][1]);
	}
	print(ans);
	return 0;
}