solution
该博文刚写完,就不小心手残清空了,只好重写。
生成函数练手题
先写上这个式子
题目中描述了两种限制。
第一种限制:神石的块数必须是的倍数,那么他的生成函数就是。这就相当于用替换掉了上方式子中的。所以该生成函数就是
第二中限制:神石的数目不超过,那么他的生成函数就是。我们将其看作。第一个括号里的内容就是,第二个括号里就相当于将最上方的式子每项都乘以。所以第二个括号里的内容就是。所以该限制的生成函数就是
然后将所有的限制用生成函数描述出来,并相乘,所得多项式的第项就是答案。
这10个限制的生成函数相乘为
约分一下发现就是。
由广义二项式定理
所以第n项的系数就是
n比较大,用NTT或者FFT优化高精乘即可。
code
/* * @Author: wxyww * @Date: 2020-04-16 09:31:03 * @Last Modified time: 2020-04-16 10:17:08 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 1000010,mod = 998244353; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } char s[N]; struct BIGNUM { int a[N],len; void Read() { scanf("%s",s); len = strlen(s); for(int i = 0;i < len;++i) a[i] = s[len - i - 1] - '0'; } }n,a1,a2,a3,a4; BIGNUM operator + (BIGNUM A,int x) { A.a[0] += x; for(int i = 0;i < A.len;++i) { if(A.a[i] >= 10) { A.a[i + 1] += A.a[i] / 10; A.a[i] %= 10; if(i == A.len - 1) ++A.len; } } return A; } BIGNUM operator / (BIGNUM A,int x) { int now = 0; for(int i = A.len - 1;i >= 0;--i) { now = now * 10 + A.a[i]; A.a[i] = now / x; now %= x; } while(!A.a[A.len - 1]) --A.len; return A; } int qm(int x,int y) { int ret = 1; for(;y;y >>= 1,x = 1ll * x * x % mod) if(y & 1) ret = 1ll * ret * x % mod; return ret; } int rev[N]; void NTT(int *a,int n,int xs) { for(int i = 0;i <= n;++i) if(rev[i] > i) swap(a[i],a[rev[i]]); for(int m = 2;m <= n;m <<= 1) { ll w1 = qm(3,(mod - 1) / m); if(xs == -1) w1 = qm(w1,mod - 2); for(int i = 0;i < n;i += m) { ll w = 1; for(int k = 0;k < (m >> 1);++k) { ll u = a[i + k],t = w * a[i + k + (m >> 1)] % mod; a[i + k] = (u + t) % mod;a[i + k + (m >> 1)] = (u - t + mod) % mod; w = w * w1 % mod; } } } } int t1[N],t2[N]; BIGNUM operator * (const BIGNUM &A,const BIGNUM &B) { int len = A.len + B.len - 1; int tot = 1; while(tot <= len) tot <<= 1; // printf("!!!%d\n",tot); for(int i = 0;i <= tot;++i) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? (tot >> 1) : 0); memset(t1,0,sizeof(t1));memset(t2,0,sizeof(t2)); for(int i = 0;i < A.len;++i) t1[i] = A.a[i]; for(int i = 0;i < B.len;++i) t2[i] = B.a[i]; // printf("%d\n",tot); NTT(t1,tot,1);NTT(t2,tot,1); for(int i = 0;i <= tot;++i) t1[i] = 1ll * t1[i] * t2[i] % mod; NTT(t1,tot,-1); // for(int i = 0;i <= tot;++i) printf("%d ",t1[i]); puts(""); int tmp = qm(tot,mod - 2); BIGNUM C; C.len = len; for(int i = 0;i <= tot;++i) t1[i] = 1ll * t1[i] * tmp % mod; for(int i = 0;i < C.len;++i) { if(t1[i] >= 10) { t1[i + 1] += t1[i] / 10; t1[i] %= 10; if(i == C.len - 1) ++C.len; } C.a[i] = t1[i]; // printf("%d ",t1[i]); } // printf("%d%d\n",C.a[0],C.a[1]); // puts(""); return C; } int main() { n.Read(); // BIGNUM K = (n + 1) * (n + 2); BIGNUM K = (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24; for(int i = K.len - 1;i >= 0;--i) printf("%d",K.a[i]); return 0; }