kmjp's blog

競技プログラミング参加記です

Codeforces #736 Div1 : C. The Three Little Pigs

もっと問題文短くなると良いな。
https://codeforces.com/contest/1548/problem/C

問題

N日間の間、毎日3匹ずつ豚が増える広場を考える。
以下のクエリについて答えよ。

  • 整数Xが与えられる。オオカミはある日M匹以上の豚がいるときに広場に来て、X匹の豚を食べる。
  • オオカミの来る日付と食べる豚の組み合わせは計何通りか。

解法

求めたい値をf(M)とすると、以下のようになる。
 \displaystyle f(M) = \sum_{i=1}^N C(3\times i, M)

FPSを使うと、下記を求めればよい。
 \displaystyle f(M) = [x^M](1+(1+x)^{3}+(1+x)^{6}+...+(1+x)^{3N}) =  [x^M] \frac{(1+x)^{3N+3}-1}{(1+x)^3-1}

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考えず解いてる気もするな…。