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;
}