[LOJ 6485] LJJ 学二项式定理

LOJ 6485

思路

设$f(x)=\sum \limits_{i=0}^n\left({n\choose i}\cdot s^i\cdot x^i\right)=(sx+1)^n$
$$\begin{split}\sum \limits_{i=0}^n \left( {n\choose i} \cdot s^{i} \cdot a_{i\bmod 4} \right)
&=\sum \limits_{t=0}^3 \left(\sum \limits_{i=0}^n\left({n\choose i}\cdot s^i\cdot a_{t}\cdot [4|i-t]\right)\right)\\
&=\sum \limits_{t=0}^3 \left(\sum \limits_{i=0}^n\left({n\choose i}\cdot s^i\cdot a_{t}\cdot \frac{1}{4}\cdot \sum \limits_{j=0}^{3}\omega^{j\cdot (i-t)}\right)\right)\\
&=\frac{1}{4}\cdot \sum \limits_{t=0}^3 \left(a_{t}\cdot \sum \limits_{j=0}^{3}\frac{\sum \limits_{i=0}^n\left({n\choose i}\cdot s^i\cdot \omega^{ji}\right)}{\omega^{jt}}\right)\\
&=\frac{1}{4}\cdot \sum \limits_{t=0}^3\left(a_t\cdot \sum \limits_{i=0}^3\frac{f(\omega^i)}{\omega^{it}}\right)
\end{split}$$

顺便吐槽一句,NOI版的编译器编译出来的跑得是真的慢

代码

#include <iostream>
#include <cstdio>

template <typename T> void in(T &_){
    char c=getchar(); while(c<'0'||c>'9') c=getchar();
    _=0; while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar();
}
template <typename T, typename ...A> void in(T &_, A &...a){in(_); in(a...);}

typedef long long LL;
const int MOD=998244353, W[5]={1, 911660635, 998244352, 86583718, 1}, inv4=748683265;
LL N;
int s, a[4], qwq[4];

int ksm(int _, LL __){
    int ans=1;
    while(__){
        if(__&1) ans=1LL*_*ans%MOD;
        _=1LL*_*_%MOD; __>>=1;
    }
    return ans;
}

int main(){
    int T; in(T); N%=MOD-1;
    while(T--){
        in(N, s, a[0], a[1], a[2], a[3]);
        int ans=0;
        for(int i=0; i<4; i++) qwq[i]=ksm((1LL*s*W[i]+1)%MOD, N);
        for(int t=0; t<4; t++){
            int tmp=0;
            for(int i=0; i<4; i++) tmp=(tmp+1LL*qwq[i]*W[4-i*t%4]%MOD)%MOD;
            ans=(ans+1LL*tmp*a[t]%MOD)%MOD;
        }
        ans=1LL*ans*inv4%MOD;
        printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注