LibreOJ 6485 LJJ 学二项式定理

花了几分钟时间学单位根反演 /cy /cy /cy
对没错我就是打算先做 HNOI2019 D2T2 再做 D2T1（

考虑求 4∑i=0aici，其中 ci=n∑j=0(nj)sj[j≡i(mod4)]

那么设个 f(x)=n∑i=0(ni)si=(sx+1)n

然后套单位根反演有 c4−i=n+i∑j=i(nj−i)sj−i[4∣j]=143∑j=0f(ωj4)ωij4=143∑j=0(sωj4+1)nωij4

代码：

#include <cstdio>
using namespace std;
const int mod = 998244353;
const int inv = 748683265;
const int G = 3;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int T;
long long n;
int s,a[4],rt[4],ans;
int main()
{
    for(register int i = 0;i < 4;++i)
        rt[i] = fpow(G,(mod - 1) / 4 * i);
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%lld%d%d%d%d%d",&n,&s,a,a + 1,a + 2,a + 3),n %= (mod - 1),ans = 0;
        for(register int i = 0,c;i < 4;++i)
        {
            c = 0;
            for(register int j = 0;j < 4;++j)
                c = (c + (long long)fpow(((long long)s * rt[j] + 1) % mod,n) * rt[j * (4 - i) % 4]) % mod;
            c = (long long)c * inv % mod,
            ans = (ans + (long long)c * a[i]) % mod;
        }
        printf("%d\n",ans);
    }
}