:::info[Description] Link. :::
:::infoSolution 题目中给的式子相当于是 。直接算肯定是不行的，容易想到把这个东西用 GF 或者 dp 来求，这里给出一个 dp 求的做法：
设 （），则要求的式子就是 。考虑对着这个和式做一些手脚让这个 dp 是可以递推的：
（）。
。
边界情况是 。直接递推时间复杂度就是线性的。 :::
:::success[Code]
namespace lowspeed_song {
int fac[N], inv[N], ifac[N], pwr[N], ipwr[N];
inline void init() {
fac[0] = inv[0] = ifac[0] = 1;
fac[1] = inv[1] = ifac[1] = 1;
for (int i = 2; i < N; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
pwr[0] = ipwr[0] = 1;
for (int i = 1; i < N; ++i) {
pwr[i] = pwr[i - 1] * 2 % mod;
ipwr[i] = ipwr[i - 1] * i2 % mod;
}
}
inline int binom(int a, int b) {
if (b < 0 || a < b) return 0;
return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
int f[N][3];
const int i3 = inversion(3);
inline void sol() {
int n, q; cin >> n >> q;
f[0][0] = f[0][1] = f[0][2] = n + 1;
for (int i = 1; i <= 3 * n; ++i) {
f[i][0] = (binom(3 * n + 3, i + 1) - 2 * f[i - 1][0] - f[i - 1][1] + 3 * mod) % mod * i3 % mod;
f[i][1] = (f[i][0] + f[i - 1][0]) % mod;
f[i][2] = (f[i][1] + f[i - 1][1]) % mod;
}
while (q--) {
int x; cin >> x;
cout << f[x][0] << '\n';
}
}
} // namespace lowspeed_song:::
难度：蓝
鲜活指数：2
喜欢的话，留下你的评论吧～