Submission #5413839

---

Source Code Expand

#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
/*
数え上げpdfを読んで
３条件を満たせば全て作れる
・各桁の和がM以下
・1から引いたやつの各桁の和がN以下
・各桁の和はM-a(K-1)
この3つを満たせばいいのはどうして？
3つ目の条件と同じ数になるように最初に1を消してしまうことは出来るし、0も同じようにして減らせる
そうしたら各桁に対してそれを集めてそれとぎゅってすればおっけー
たとえば0.304が作りたかったらまず1を7個、0を3K-9個にした後、1を4個と0をK-4個でぎゅってして、
出来た0.4と0をK-1個でぎゅってして、出来た0.04と1を3個と0をK-4個ぎゅってすればオッケー
*/
int dp[5010][5010];
//main
signed main(){
  int N,M,K;cin>>N>>M>>K;
  std::vector<int> w(5015,0);
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(int i=0;i<=5000;i++){
    for(int j=0;j<=5000;j++)w[j+1]=(w[j]+dp[i][j])%MOD;
    for(int j=0;j<=5000;j++)dp[i+1][j]=(w[j+1]-w[max(0LL,j-(K-1))]+MOD)%MOD;
  }
  int ans=0;
  for(int i=0;i<=5000;i++){
    for(int j=1;j<=5000;j++){
      if(M-j>=0&&(M-j)%(K-1)==0&&i*(K-1)+1-j==N)ans+=dp[i][j];
      ans%=MOD;
    }
  }
  cout<<ans<<endl;
}

Submission Info

Judge Result