LJJ 学二项式定理

题意

\(T\)组数据，每组给定\(n,s,a_0,a_1,a_2,a_3\)，求
\[ \sum_{i=0}^n \binom{n}{i}s^ia_{i\bmod 4} \]
对\(998244353\)取模

范围

\(1\le T\le 10^5,1\le n\le 10^{18},1\le s,a_0,a_1,a_2,a_3\le 10^8\)

单位根反演有个套路
\[ [k\equiv l \ (\text{ mod } n)\ ]=\frac{1}{n}\sum_{i=0}^{n-1}w_n^{(k-l)} \]
然后用套路推柿子
\[ \begin{aligned} &\sum_{i=0}^n\binom{n}{i}s^ia_{i \bmod 4}\=&\sum_{d=0}^3a_d\sum_{i=0}^n\binom{n}{i}s_i[i\equiv d\bmod 4]\=&\sum_{d=0}^3a_d\sum_{i=0}^n\binom{n}{i}s_i(\frac{1}{4}\sum_{j=0}^3w_4^{(i-d)j})\=&\frac{1}{4}\sum_{d=0}^3a_d\sum_{j=0}^3\sum_{i=0}^nw_4^{(i-d)j}\binom{n}{i}s^i\=&\frac{1}{4}\sum_{d=0}^3a_d\sum_{j=0}^3w_4^{-dj}\sum_{i=0}^n\binom{n}{s}(sw_4^j)^i\=&\frac{1}{4}\sum_{d=0}^3a_d\sum_{j=0}^3w_4^{-dj}(sw_4^j+1)^n \end{aligned} \]

Code:

#include <cstdio>
#include <cctype>
#define ll long long
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
template <class T>
void read(T &x)
{
    x=0;char c=gc();
    while(!isdigit(c)) c=gc();
    while(isdigit(c)) x=x*10+c-'0',c=gc();
}
const int mod=998244353;
const int inv4=748683265;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*(a)*(b)%mod)
int qp(int d,int k)
{
    int f=1;
    while(k)
    {
        if(k&1) f=mul(f,d);
        d=mul(d,d);
        k>>=1;
    }
    return f;
}
int w[4],a[4],s;
ll n;
int main()
{
    int T;read(T);
    w[0]=1,w[1]=qp(3,mod-1>>2),w[2]=mod-1,w[3]=mul(w[1],w[2]);
    while(T--)
    {
        read(n),read(s);
        int ans=0;
        for(int a,i=0;i<4;i++)
        {
            read(a);int sum=0;
            for(int j=0;j<4;j++)
            {
                int f=add(mul(s,w[j]),1);
                sum=add(sum,mul(w[(20-i*j)%4],qp(f,n%(mod-1))));
            }
            ans=add(ans,mul(a,sum));
        }
        ans=mul(ans,inv4);
        printf("%d\n",ans);
    }
    return 0;
}

2019.5.7

LOJ6485 LJJ 学二项式定理 解题报告

原文：https://www.cnblogs.com/butterflydew/p/10828376.html