Codeforces Round 736 (Div. 2) E - The Three Little Pigs

Codeforces Round 736 (Div. 2) E - The Three Little Pigs

八月 03, 2021

题目概述

对于一个$n$,给定$q$​​次询问,回答

数据范围

分析与解

这个题主要考察组合恒等式的运用，或者用生成函数的方法。

解法1

我们首先肯定有两个组合恒等式

其中第二个式子可以用数学归纳法结合第一个式子证明。

因此针对本题3的倍数这一特点，我们考虑通过剩余类来DP

定义

则我们有递推式

求解这三个方程并递推便能预处理得到所有的情况。

最t后答案便是

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 3001000
const int MOD = 1e9+7;
int n,q;
LL fac[MAXN],inv[MAXN];
LL dp[MAXN][3];
LL quick_pow(LL a,LL b) {
	LL ret=1;
	while(b) {
		if(b & 1)ret=ret*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ret;
}
LL Combo(int n,int m) {
	if(n<0 || m<0 || n<m)return 0;
	return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main() {
	int x;
	LL div3=quick_pow(3,MOD-2);
	scanf("%d%d",&n,&q);
	fac[0]=1;
	for(int i=1; i<=3*n; i++)fac[i]=1ll*i*fac[i-1]%MOD;
	//加速方法 
	inv[3*n]=quick_pow(fac[3*n],MOD-2);
	for(int i=3*n-1; i>=0; i--)inv[i]=inv[i+1]*(i+1)%MOD;
	dp[0][0]=dp[0][1]=dp[0][2]=n;
	for(int i=1; i<=3*n; i++) {
		dp[i][0]=(Combo(3*n,i+1)-1ll*2*dp[i-1][0]%MOD-dp[i-1][1]+1ll*3*MOD)*div3%MOD;
		dp[i][1]=(dp[i][0]+dp[i-1][0]+MOD)%MOD;
		dp[i][2]=(dp[i][1]+dp[i-1][1]+MOD)%MOD;
	}
	while(q--) {
		scanf("%d",&x);
		printf("%lld\n",(dp[x][0]+Combo(3*n,x)+MOD)%MOD);
	}
	return 0;
}

解法2

这道题求解时的瓶颈就是组合数如何生成？除了上面解法1通过组合恒等式来DP外，我们可以结合二项式定理和生成函数的思路。

考虑

该幂级数展开后，$t^x$​的系数就是我们所求的答案。所以我们可以计算这个级数的系数表示，即可。

这个式子模拟大除法即可。由于分母很容易得到系数，分子通过组合数预处理，所以线性就可以求出所有系数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//cancel k from numerator and denominator of P(k)
   vl num(M,0);
   REP(i,M) {
       num[i] = c.choose(M,i+1);
       if (i <= 2) {
           num[i] -= c.choose(3,i+1);
           num[i] = (num[i]+MOD)%MOD;
       }
   }
   //denominator is k^2+3k+3
   //P(k) is num/denominator

   vl P(3*N+1,0);
   for (int i = 3*N; i >= 0; i--) {
       P[i] = num[i+2];
       num[i+1] = (num[i+1]-3*P[i]+3*MOD)%MOD;
       num[i] = (num[i]-3*P[i]+3*MOD)%MOD;
   }