結果
問題 | No.503 配列コレクション |
ユーザー |
![]() |
提出日時 | 2017-03-18 13:40:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 543 ms / 2,000 ms |
コード長 | 2,205 bytes |
コンパイル時間 | 545 ms |
コンパイル使用メモリ | 66,612 KB |
実行使用メモリ | 34,776 KB |
最終ジャッジ日時 | 2024-07-04 19:10:27 |
合計ジャッジ時間 | 3,724 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include <iostream>using namespace std;int64_t extgcd(int64_t a, int64_t b, int64_t&x, int64_t&y){int64_t d=a;if(b!=0){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}else{x=1;y=0;}return d;}int64_t mod_pow(int64_t a, int64_t e, int64_t p){int64_t res = 1;for(;e>0;e>>=1){if(e&1)res=(res*a)%p;a=(a*a)%p;}return res;}int64_t mod_inverse(int64_t a, int64_t m){int64_t x, y;extgcd(a,m,x,y);return (m+x%m)%m;}int64_t fact(int64_t n, int64_t p){static int64_t F[1000001];if(F[n]) return F[n];else{F[0]=1;for(int64_t i=1;i<=1000000;i++){F[i]=i*F[i-1]%p;}return F[n];}int64_t res=1;while(n){res*=n;if(res>p)res%=p;if(res==0)return 0;n--;}return res;}int64_t mod_fact(int64_t n,int64_t p,int64_t &e){static int64_t F[1000001];if(F[n]) return F[n];e=0;if(n==0)return 1;int64_t res=mod_fact(n/p,p,e);e+=n/p;if(n/p%2!=0) return F[n]=res*(p-fact(n%p,p))%p;return F[n]=res*fact(n%p,p)%p;}int64_t mod_comb(int64_t n, int64_t k,int64_t p){if(n<0||k<0||n<k)return 0;int64_t e1,e2,e3;int64_t a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);//if(e1>e2+e3)return 0;//return (a1*mod_inverse(a2*a3%p,p))%p;return a1*mod_pow(a2*a3%p,p-2,p)%p;}int main(){int64_t N,K,D;cin>>N>>K>>D;int cnt = N/(K-1)-(N%(K-1)==0);// int cnt = (N-1)/(K-1);int len = N-cnt*(K-1);if(D==1){cout<<len<<endl;return 0;}int64_t alpha[2][cnt+1],beta[2][cnt+1];fill(alpha[0],alpha[2],0);fill(beta[0],beta[2],0);int64_t mod = 1e9+7;for(int j=0;j<=cnt;j++){beta[1][j]=mod_pow(D,j,mod);}for(int i=2;i<=len;i++){alpha[i&1][0]=i-1;beta[i&1][0]=1;for(int j=0;j<cnt;j++){alpha[i&1][j+1]=(alpha[i&1][j]+alpha[i&1^1][j+1]+beta[i&1^1][j+1])%mod;beta[i&1][j+1]=(mod_comb(i+j-1,i-2,mod)+D*beta[i&1][j])%mod;}}cout<<(alpha[len&1][cnt]+beta[len&1][cnt])%mod<<endl;return 0;}