問題はこちら
No.269 見栄っ張りの募金活動 - yukicoder
これはメモ化再帰が書きやすかった
予めKの分を処理しておくことでK=0の場合に帰着すると良い
int a[101][20001],l[101][20001]; int f(int n,int s){ //k=0のときn人でちょうどs円払う方法 if(l[n][s]++)return a[n][s]; if(n==0)return !s; //0円は0人で払える return a[n][s]=(f(n-1,s)+(s<n?0:f(n,s-n)))%1000000007; //1人目が1円も払わない場合f(n-1,s) //1人目が"とりあえず"1円払う場合、n人全体でn円払うことが確定するので //残りn人でs-n円 } int main(){ int n,s,k,i,j; scanf("%d%d%d",&n,&s,&k); s-=n*(n-1)/2*k; //kの分を処理 if(s<0)puts("0"); else printf("%d",f(n,s)); return 0; }
K=0の場合「i番目の人は、i-1番目の人より(≧0)円多く払うときの合計金額」を考えることになる(iは1-basedで、とおく)
この時、i番目の人が払う金額はなので、合計金額はとなる。
各が何回登場するかを考えて和の順を変えるととなる。
よって結局、問題は次のように読み替えられる
「n,sが与えられた時、を満たすようなの組は何通りあるか?」
さらにaのindexを逆にする、すなわちをと置き換えることで目的の式はとなるので、これは「1~n円玉でちょうどs円払う方法は何通りか?」となりyukicoder No.41 貯金箱の溜息(EASY) - メモと同様の方法で求める事ができる
(No.41は「s円"以下"」であり、こちらは「"ちょうど"s円」という違いがある点に注意)
a['~~'],i,n,s,m=1e9+7; main(j){ *a=1; scanf("%d%d%d",&n,&s,&j); s-=~-n*n/2*j; for(i=1;i<=n;i++)for(j=1;j<s;j++)a[j+i]=(a[j+i]+a[j])%m; i=!printf("%d",s<0?0:a[s]); }
(なお「a['~~']={1};」と記述するとFile size limit exceededなるエラーが出る。参考:C/C++でグローバル変数(配列)を0以外に初期化すると実行ファイルが巨大になる罠 - Qiita)
ということでこれを縮めて
a['~~'],i,n,s,m=1e9+7; main(j){ *a=1; scanf("%d%d%d",&n,&s,&j); for(s-=~-n*n/2*j;i++<n;)for(j=i-1;j++<s;a[j]%=m)a[j]+=a[j-i]; i=!printf("%d",s<0?0:a[s]); }
ポインタを使うと1B縮んで
a['~~'],i,n,s,m=1e9+7,*p; main(j){ *a=1; scanf("%d%d%d",&n,&s,&j); for(s-=~-n*n/2*j;i++<n;)for(p=a;p-a<s;p++[i]%=m)p[i]+=*p; i=!printf("%d",s<0?0:a[s]); }
148B