题解：AT_arc102_c [ARC102E] Stop. Otherwise...

· · 题解

这是生成函数的另一种做法。

容易发现答案是对称的，所以我们只需要求解 x\in [2,K+1] 中的答案。

我们考虑的对象是大小为 s 的骰子的个数。可以注意到，对于每个要求解的 x，我们会产生 T 对互相限制的二元组（具体而言，T=\min(x-1,k)），每组中的和为 x ,而这些组其它方面都一样，所以我们可以将一个组作为一个对象考虑。

对于一个组，其选出 0 个骰子（不选）的方案数为 1，其余为 2。所以其的生成函数为：

1+\sum_{i=1}^\infin 2x^i=1+\frac{2x}{1-x}=\frac{1+x}{1-x}

一种特殊情况是点数为 \frac{x}{2} 的骰子（如果存在的话），不过这种情况我们之后特判可以解决。（其只可能选一个或是不选）

对于没有受到限制的骰子种类，其的选择方案数为：

\sum^\infin_{i=0}x^i=\frac{1}{1-x}

对于同一个 T ,我们需要考虑的一类对象有 \lfloor \frac T2 \rfloor 个，需要考虑的二类对象有 k-T 个（无论点数为 \frac x2 的骰子选没选）。那么整体的式子就是：

(\frac{1+x}{1-x})^{\lfloor \frac T2\rfloor}(\frac{1}{1-x})^{k-T}

之前的题解要把这个东西展开，但是实际上不用。我们可以发现 T 每次的变化幅度是很小的，所以我们可以直接维护这个式子（展开式）。

总复杂度 O(nk)。

注意多项式除法可以以多项式乘法的逆过程实现。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005,mod=998244353;
int n,k,f[N];
inline void c1(){// /(1-x) 
    for(int i=0;i<=n;i++) (f[i+1]-=f[i]*-1)%=mod;
}
inline void c2(){// *(1+x) 
    for(int i=n;i>=0;i--) (f[i+1]+=f[i]*1)%=mod;
}
inline void c3(){// *(1-x) 
    for(int i=n;i>=0;i--) (f[i+1]+=f[i]*-1)%=mod;
}
inline int calc(int T){
    return ((f[n]+(T%2?f[n-1]:0))%mod+mod)%mod;
}
int ans[N*2];
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>k>>n;

    f[0]=1;
    for(int i=1;i<=k;i++) c1();
    int T=0;
    for(int s=1;s<=k+1;s++){
        int NT=min(s-1,k);
        if(NT>T){
            if(NT/2!=T/2) c2();
            else c3();
        }
        T=NT;
        if(s!=1) ans[s-1]=calc(T);
    }
    for(int i=1;i<=k;i++) ans[k+i]=ans[k-i];
    for(int i=1;i<=k*2-1;i++) cout<<ans[i]<<"\n";
    return 0;
}