PKU 2992 Divisors
http://poj.org/problem?id=2992
nCkの約数の個数を求める。(0<=k<=n<=431)
cinの遅さを改めて実感しました。
あと、高速化するのが大変でした。
素因数分解して事前計算して、頑張りました。
map<int,int> fac[432]; ll ans[432][432]; map<int,int> ret; map<int,int> fact(int in){ ret.clear(); for(int i=2;i*i<=in;i++){ if(in%i)continue; do{ ret[i]++; in/=i; }while(in%i==0); } if(in>1)ret[in]++; return ret; } map<int,int> tt; main(){ rep(i,432){ fac[i]=fact(i); } rep(n,432){ tt.clear(); rep(k,n+1){ if(ans[n][min(k,n-k)])break; if(0<k)FOR(miter,fac[n-k+1])tt[miter->F]+=miter->S; FOR(miter,fac[k])tt[miter->F]-=miter->S; ll tans=1; FOR(miter,tt){ tans*=miter->S+1; } ans[n][k]=tans; } } int n,k; while(~scanf("%d%d",&n,&k))cout<<ans[n][min(k,n-k)]<<endl; }