もっと問題文短くなると良いな。
https://codeforces.com/contest/1548/problem/C
問題
N日間の間、毎日3匹ずつ豚が増える広場を考える。
以下のクエリについて答えよ。
- 整数Xが与えられる。オオカミはある日M匹以上の豚がいるときに広場に来て、X匹の豚を食べる。
- オオカミの来る日付と食べる豚の組み合わせは計何通りか。
解法
求めたい値をf(M)とすると、以下のようになる。
FPSを使うと、下記を求めればよい。
int N,Q; const ll mo=1000000007; ll comb(ll N_, ll C_) { const int NUM_=4400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll A[3030303]; ll B[3030303]; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&Q); assert(N<=1000000); FOR(i,3*N) { ll x=comb(3*N,i+1); (A[i]+=x)%=mo; (A[i+1]+=3*x)%=mo; (A[i+2]+=3*x)%=mo; (A[i+3]+=x)%=mo; } for(i=3*N+5;i>=2;i--) { B[i-2]=A[i]; (A[i-1]+=(mo-A[i])*3)%=mo; (A[i-2]+=(mo-A[i])*3)%=mo; } assert(A[0]==0); assert(A[1]==0); FOR(i,Q) { scanf("%d",&x); _P("%d\n",(int)B[x]); } }
まとめ
本番はFPS考えず解いてる気もするな…。