题意
这道题实际上就是让求 ∑ i = 1 n C 3 ∗ i x , x \displaystyle\sum_{i=1}^{n}C_{3*i}^x,x i=1∑nC3∗ix,x是我们每次询问的数值， n n n是小猪进场的轮数。
思路
我们可以定义一个
d
p
dp
dp方程，
d
p
[
x
]
[
m
]
dp[x][m]
dp[x][m]代表
∑
i
=
1
n
−
1
C
3
∗
i
+
m
x
\displaystyle\sum_{i=1}^{n-1}C_{3*i+m}^x
i=1∑n−1C3∗i+mx
因此，我们可以得到
d
p
[
x
]
[
0
]
+
d
p
[
x
]
[
1
]
+
d
p
[
x
]
[
2
]
=
∑
i
=
1
3
∗
n
−
1
C
i
x
dp[x][0]+dp[x][1]+dp[x][2]=\displaystyle\sum_{i=1}^{3*n-1}C_{i}^x
dp[x][0]+dp[x][1]+dp[x][2]=i=1∑3∗n−1Cix
又根据杨辉三角的性质我们可以得到
C i x + C i x − 1 = C i + 1 x C_i^x+C_i^{x-1}=C_{i+1}^x Cix+Cix−1=Ci+1x
因此
d
p
[
x
]
[
1
]
=
d
p
[
x
]
[
0
]
+
d
p
[
x
−
1
]
[
0
]
dp[x][1]=dp[x][0]+dp[x-1][0]
dp[x][1]=dp[x][0]+dp[x−1][0]
d
p
[
x
]
[
2
]
=
d
p
[
x
]
[
1
]
+
d
p
[
x
−
1
]
[
1
]
dp[x][2]=dp[x][1]+dp[x-1][1]
dp[x][2]=dp[x][1]+dp[x−1][1]
又根据公式
∑
i
=
k
n
C
i
k
=
C
n
+
1
k
+
1
\displaystyle\sum_{i=k}^{n}C_{i}^k=C_{n+1}^{k+1}
i=k∑nCik=Cn+1k+1
因此
d
p
[
x
]
[
0
]
+
d
p
[
x
]
[
1
]
+
d
p
[
x
]
[
2
]
=
C
3
∗
n
x
+
1
dp[x][0]+dp[x][1]+dp[x][2]=C_{3*n}^{x+1}
dp[x][0]+dp[x][1]+dp[x][2]=C3∗nx+1
现在递推式每一个状态下的
d
p
[
x
]
[
1
]
,
d
p
[
x
]
[
2
]
dp[x][1],dp[x][2]
dp[x][1],dp[x][2]都能求出来了，现在就来求
d
p
[
x
]
[
0
]
dp[x][0]
dp[x][0]
根据上述方程。
d
p
[
x
]
[
1
]
=
d
p
[
x
]
[
0
]
+
d
p
[
x
−
1
]
[
0
]
dp[x][1]=dp[x][0]+dp[x-1][0]
dp[x][1]=dp[x][0]+dp[x−1][0]
d
p
[
x
]
[
2
]
=
d
p
[
x
]
[
1
]
+
d
p
[
x
−
1
]
[
1
]
dp[x][2]=dp[x][1]+dp[x-1][1]
dp[x][2]=dp[x][1]+dp[x−1][1]
d
p
[
x
]
[
0
]
+
d
p
[
x
]
[
1
]
+
d
p
[
x
]
[
2
]
=
C
3
∗
n
x
+
1
dp[x][0]+dp[x][1]+dp[x][2]=C_{3*n}^{x+1}
dp[x][0]+dp[x][1]+dp[x][2]=C3∗nx+1
代入原方程求得：
d
p
[
x
]
[
0
]
+
d
p
[
x
]
[
0
]
+
d
p
[
x
−
1
]
[
0
]
+
d
p
[
x
]
[
1
]
+
d
p
[
x
−
1
]
[
1
]
=
C
3
∗
n
x
+
1
dp[x][0]+dp[x][0]+dp[x-1][0]+dp[x][1]+dp[x-1][1]=C_{3*n}^{x+1}
dp[x][0]+dp[x][0]+dp[x−1][0]+dp[x][1]+dp[x−1][1]=C3∗nx+1
d
p
[
x
]
[
0
]
+
d
p
[
x
]
[
0
]
+
d
p
[
x
−
1
]
[
0
]
+
d
p
[
x
]
[
0
]
+
d
p
[
x
−
1
]
[
0
]
+
d
p
[
x
−
1
]
[
1
]
=
C
3
∗
n
x
+
1
dp[x][0]+dp[x][0]+dp[x-1][0]+dp[x][0]+dp[x-1][0]+dp[x-1][1]=C_{3*n}^{x+1}
dp[x][0]+dp[x][0]+dp[x−1][0]+dp[x][0]+dp[x−1][0]+dp[x−1][1]=C3∗nx+1
整理一下：
3 ∗ d p [ x ] [ 0 ] + 2 ∗ d p [ x − 1 ] [ 0 ] + d p [ x − 1 ] [ 1 ] = C 3 ∗ n x + 1 3*dp[x][0]+2*dp[x-1][0]+dp[x-1][1]=C_{3*n}^{x+1} 3∗dp[x][0]+2∗dp[x−1][0]+dp[x−1][1]=C3∗nx+1
因此
d p [ x ] [ 0 ] = ( C 3 ∗ n x + 1 − 2 ∗ d p [ x − 1 ] [ 0 ] − d p [ x − 1 ] [ 1 ] ) / 3 dp[x][0]=(C_{3*n}^{x+1}-2*dp[x-1][0]-dp[x-1][1])/3 dp[x][0]=(C3∗nx+1−2∗dp[x−1][0]−dp[x−1][1])/3
同时，官方题解的逆元求组合数的板子比我的强了不知道多少倍。
#include<vector>
#define vi vector<int>
#define vl vector<long long>
typedef long long ll;
const ll MOD=1e9+7;
struct Combo {
vl facs;
vl invfacs;
int N;
Combo(int N) {
this->N=N;
facs.assign(N+1,0);
invfacs.assign(N+1,0);
facs[0] = 1;
for (int i = 1; i <= N; i++) {
facs[i] = (facs[i-1]*i)%MOD;
}
invfacs[N] = power(facs[N],MOD-2);
for (int i = N-1; i >= 0; i--) {
invfacs[i] = (invfacs[i+1]*(i+1))%MOD;
}
}
ll choose(int n, int k) {
if (n<0||k<0||n<k) return 0LL;
ll denInv = (invfacs[k]*invfacs[n-k])%MOD;
ll ans = (facs[n]*denInv)%MOD;
return ans;
}
ll power(ll x, ll y) {
ll ans = 1;
x %= MOD;
while (y > 0) {
if (y%2==1) ans = (ans*x)%MOD;
y /= 2;
x = (x*x)%MOD;
}
return ans;
}
};
#include<iostream>
#include<vector>
#define vi vector<int>
#define vl vector<long long>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
const int M=3e6+5;
const ll MOD=1e9+7;
struct Combo {
vl facs;
vl invfacs;
int N;
Combo(int N) {
this->N=N;
facs.assign(N+1,0);
invfacs.assign(N+1,0);
facs[0] = 1;
for (int i = 1; i <= N; i++) {
facs[i] = (facs[i-1]*i)%MOD;
}
invfacs[N] = power(facs[N],MOD-2);
for (int i = N-1; i >= 0; i--) {
invfacs[i] = (invfacs[i+1]*(i+1))%MOD;
}
}
ll choose(int n, int k) {
if (n<0||k<0||n<k) return 0LL;
ll denInv = (invfacs[k]*invfacs[n-k])%MOD;
ll ans = (facs[n]*denInv)%MOD;
return ans;
}
ll power(ll x, ll y) {
ll ans = 1;
x %= MOD;
while (y > 0) {
if (y%2==1) ans = (ans*x)%MOD;
y /= 2;
x = (x*x)%MOD;
}
return ans;
}
};
ll dp[M][4];
int main(){
ll n;
cin>>n;
Combo c(3*n);
ll inv=c.power(3,MOD-2);
dp[0][0]=dp[0][1]=dp[0][2]=n;
for(int i=1;i<n*3;i++){
dp[i][0]=(c.choose(3*n,i+1)-2*dp[i-1][0]-dp[i-1][1]+3*MOD)*inv%MOD;
dp[i][1]=(dp[i-1][0]+dp[i][0])%MOD;
dp[i][2]=(dp[i-1][1]+dp[i][1])%MOD;
}
int m;
cin>>m;
while(m--){
int q;
scanf("%d",&q);
printf("%lld\n",(ll)(dp[q][0]+c.choose(3*n,q))%MOD);
}
}