CF1548C The Three Little Pigs
前置知识
题目大意
给定 n 和若干 x,对每个 x 求 ∑i=1n(x3i)。
其中 1≤n≤106,1≤x≤3n。
题解
这里需要用到一个小技巧,对于在求和中的组合数,可以利用递推公式将其拆开,然后化简出求和的递推公式。
显然我们需要拆式子:
(x3i)=(x3i−1)+(x−13i−1)=(x3i−2)+(x−13i−2)+(x−13i−2)+(x−23i−2)=(x3i−3)+3×(x−13i−3)+3×(x−23i−3)+(x−33i−3)
设 S(x)=i=1∑n(x3i),接下来找一下 i=1∑n(y3i−3) 与 S(3x) 的关系:
i=1∑n(y3i−3)=(y0)+(y3)+⋯+(y3n−3)=S(y)−(y3n)+(y0)
并且有两个恒等式:
(x3n)+3×(x−13n)+3×(x−23n)+(x−33n)=k=0∑3(k3)×(x−k3n)=(x3n+3)(x0)+(x−10)+(x−20)+(x−30)=k=0∑3(k3)×(x−k3−3)=(x3)
将其带入,消去 S(x),得到:
(x3n+3)−(x+13)=3×S(x−1)+3×S(x−2)+S(x−3)
将 x 替换为 x+1,变形得到:
S(x)=31[(x+13n+3)−(x+13)−S(x−2)]−S(x−1)
这便是能够直接转移的公式,只需要线性处理逆元即可。
对于边界,显然有 S(0)=n,S(1)=23n(n+1)。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
const LL M = 1e9+7;
int n , m;
LL fac[N*3] , inv[N*3];
LL res[N*3];
LL qmi(LL a , LL b) {
LL res = 1;
while(b) {
if(b & 1) res = res * a % M;
b >>= 1; a = a * a % M;
}
return res;
}
int main() {
scanf("%d%d" , &n , &m);
fac[0] = inv[0] = 1;
fac[1] = inv[1] = 1;
for(int i = 2 ; i <= n*3+3 ; i ++) {
fac[i] = fac[i-1]*i % M;
}
inv[n*3+3] = qmi(fac[n*3+3] , M-2);
for(int i = n*3+2 ; i >= 1 ; i --) {
inv[i] = inv[i+1]*(i+1)%M;
}
res[0] = n; res[1] = (3ll*n*(n+1) % M)*inv[2] % M;
for(int i = 2 ; i <= n*3 ; i ++) {
LL t1 = 0;
if(i <= 2) t1 = (fac[3]*inv[2-i]%M)*inv[i+1]%M;
LL t2 = (fac[n*3+3]*inv[i+1] % M)*inv[n*3-i+2] % M;
res[i] = (inv[3]*2ll%M)*((t2-t1-res[i-2]+M)%M)%M;
res[i] = (res[i]-res[i-1]+M)%M;
}
while(m --) {
int x; scanf("%d" , &x);
printf("%lld\n" , res[x]);
}
return 0;
}