题解：AT_fps_24_a お菓子

· · 题解

\Large\text{Solution}

显然每天用的钱的生成函数为 x+x^3+x^4+x^6。那么 D 天用 N 元的方案数就是 [x^N](x+x^3+x^4+x^6)^D。

可以因式分解一下变成

&(x+x^3)^D(1+x^3)^D\\ =&\sum_{i=0}^D\binom{D}{i}x^ix^{3(D-i)}\sum_{j=0}^D\binom{D}{j}x^{3j} \end{aligned}

所以可以枚举第一个 i，然后就可以根据 i+3(D-i)+j=N 求出 j，也就能求出 N 次项系数。预处理组合数即可。

\Large\text{Code} 
//By _pig_&_buta_
//Ciallo～(∠・ω< )⌒★
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
#define Testify 2221
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
typedef array <int, 2> arr2;
typedef array <int, 3> arr3;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 2e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
const int mod = 998244353;
ll qmi(ll a, int b)
{
    ll t = 1;
    while (b)
    {
        if (b & 1) t = t * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return t;
}
ll fac[N], inv[N];
ll C(int a, int b)
{
    if (a < b || a < 0 || b < 0) return 0;
    return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
signed main()
{
    cin.tie (0), cout.tie (0);
    ios :: sync_with_stdio (false);
    int d, n; cin >> d >> n;
    fac[0] = inv[0] =  1;
    for (int i = 1; i <= d; i++) fac[i] = fac[i - 1] * i % mod;
    inv[d] = qmi (fac[d], mod - 2);
    for (int i = d - 1; i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
    ll ans = 0;
    for (int i = 0; i <= d; i++)
    {
        int x = i + 3 * (d - i);
        if ((n - x) % 3) continue;
        ans = (ans + C (d, i) * C (d, (n - x) / 3)) % mod;
    }
    cout << ans << "\n";
    return 0;
}//Ciallo~(∠·ω<)⌒☆