問題はこちら
No.129 お年玉(2) - yukicoder
あまりはN/1000%Mで求めることができるので、M個のぽち袋からN/1000%M個選んであたりにするので、求めるべき答えは二項係数C(M,N/1000%M)
剰余が素数なら逆元を使うことでちゃちゃっと求められるのだけど、そうじゃないので、その方法はちょっと大変
（参考：modに対するアプローチ - yukicoder）
今回はM≦10000と比較的小さいのでおとなしくパスカルの三角形により逐次計算していく
a[10010][10010]; int main(){ int i,j,m=1e9; long n; for(i=0;i<=1e4;i++)for(j=0;j<=i;j++){ if(j==0)a[i][j]=1; else a[i][j]=(a[i-1][j]+a[i-1][j-1])%m; //j==iのときa[i-1][j]は0 } scanf("%ld%d",&n,&m); printf("%d",a[m][n/1000%m]); return 0; }
特に頭を使わずに短縮
long i; a['00']['00'],m=1e9; main(j){ for(**a=1;i++<1e4;)for(j=-1;j++<i;a[i][j]=(a[i-1][j]+a[i-1][j-1])%m); scanf("%ld%d",&i,&j); m=!printf("%d",a[j][i/1000%j]); }
さて、形式的にfor文を圧縮すると
for(**a=1;i++<1e4;)for(j=-1;j++<i;a[i][j]=(a[i-1][j]+a[i-1][j-1])%m); for(**a=1;j++<i?a[i][j]=(a[i-1][j]+a[i-1][j-1])%m,1:(j=-1,i++<1e4););
となり、短くならない
そこでひらめいた。jを負の方向へ動かそう
//先ほどのfor文は for(**a=1;j++<i?a[i][j]=(a[i-1][j]+a[i-1][j-1])%m,1:(j=-1,i++<1e4);); for(**a=1;i+j--?a[i][-j]=(a[i-1][-j]+a[i-1][~j])%m,1:(j=1,i++<1e4);); //となるがよく見ると最後の部分がまとめられて for(**a=1;i+j--?a[i][-j]=(a[i-1][-j]+a[i-1][~j])%m,1:(j=i++<1e4);); //とできる
初期化をいい感じにするためにjの初期値を0にする必要があることに注意しつつ出力もまとめると
long i; a['00']['00'],m=1e9,j; main(){for(**a=1;i+j--?a[i][-j]=(a[i-1][-j]+a[i-1][~j])%m,1:(j=i++<1e4||!printf("%d",a[j][i/1000%j],scanf("%ld%d",&i,&j))););}
155B
iを負にしたりjのループを逆にしたりといった単純な工夫ではこれ以上短くできない
