[LOJ 6485] LJJ 學二項式定理

題意

給定 \(n,s,a_0,a_1,a_2,a_3\), 求:

\[ \Large \left[ \sum_{i=0}^n \left( {n\choose i} \cdot s^{i} \cdot a_{i\bmod 4} \right) \right] \bmod 998244353 \]

\(T\le 10^5\) 組測試資料, \(n\le 10^{18};s,a_i\le 10^9\).

題解

一看 \(n\) 巨大無比顯然不太能直接搞.

但是這個 \(\bmod 4\) 十分的玄妙, 我們嘗試從它入手, 分别計算每個 \(a_i\) 所産生的貢獻.

又因為組合數越界會變 \(0\), 于是答案可以寫成這樣:

\[ \sum_{k=0}^3\sum_{i\bmod 4=k} {n\choose i}a_ks^i \]

\(i\bmod 4=k\) 等價于 \(4\mid i-k\). 于是我們有:

\[ \sum_{k=0}^3\sum_{4\mid i-k} {n\choose i}a_ks^i \]

把下标換漂亮點并且把求和條件變成布爾表達式丢到和式裡:

\[ \sum_{k=0}^3\sum_{i}[4\mid i] {n\choose i+k}a_ks^{i+k} \]

然後我們如果能找個東西把 \([4\mid i]\) 反演掉就好了.

幸運的是在傅立葉變換中有個東西叫求和引理, 即當 \(k\not \mid n\) 的時候有:

\[ \sum_{j=0}^{n-1}(\omega_n^k)^j=0 \]

不難算出當 \(k\mid n\) 的時候上式的值為 \(n\). 也就是說:

\[ \frac 1 n\sum_{j=0}^{n-1}(\omega_n^k)^j=\frac 1 n\sum_{j=0}^{n-1}\omega_n^{kj}=[k\mid n] \]

那麼我們就可以把這個東西代進去按照和式的套路搞一搞求和順序和名額:

\[ \begin{aligned} &\sum_{k=0}^3\sum_{i}\left (\frac 1 4\sum_{r=0}^3\omega_4^{ir}\right) {n\choose i+k}a_ks^{i+k}\\ =&\frac 1 4\sum_{k=0}^3\sum_{r=0}^3a_k\sum_{i}{n\choose i+k}s^{i+k}\omega_4^{ir} \\ \end{aligned} \]

那麼問題變成了最内層的東西. 我們發現它有點類似二項式定理的形式, 但是 \(\omega_4^r\) 上的指數不太對. 我們強行讓它和二項式系數的部分一樣:

\[ \begin{aligned} &\frac 1 4\sum_{k=0}^3\sum_{r=0}^3a_k\sum_{i}{n\choose i+k}s^{i+k}\omega_4^{(i+k)r}\omega_4^{-kr} \\ =&\frac 1 4\sum_{k=0}^3\sum_{r=0}^3a_k\omega_4^{-kr} \sum_{i}{n\choose i+k}s^{i+k}\omega_4^{(i+k)r}\\ =&\frac 1 4\sum_{k=0}^3\sum_{r=0}^3a_k\omega_4^{-kr} \sum_{i}{n\choose i+k}(s\omega_4^r)^{i+k} \\ =&\frac 1 4\sum_{k=0}^3\sum_{r=0}^3a_k\omega_4^{-kr} (s\omega_4^r+1)^n \end{aligned} \]

然後就可以算了.

參考代碼

其實 \(\omega_4\) 就是虛數機關 \(i\)...

#include <bits/stdc++.h>

const int I=911660635;
const int NI=86583718;
const int MOD=998244353;
const int PHI=998244352;
const int INV4=748683265;
typedef long long intEx;

int Pow(int,int,int);

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        intEx n;
        int s;
        scanf("%lld%d",&n,&s);
        int ans=0;
        for(int i=0;i<4;i++){
            int a;
            scanf("%d",&a);
            for(int j=0;j<4;j++)
                (ans+=1ll*a*Pow(NI,i*j,MOD)%MOD*Pow((1ll*Pow(I,j,MOD)*s+1)%MOD,n%PHI,MOD)%MOD)%=MOD;
        }
        ans=1ll*ans*INV4%MOD;
        printf("%d\n",ans);
    }
    return 0;
}

inline int Pow(int a,int n,int p){
    int ans=1;
    while(n>0){
        if(n&1)
            ans=1ll*a*ans%p;
        a=1ll*a*a%p;
        n>>=1;
    }
    return ans;
}
                

轉載于:https://www.cnblogs.com/rvalue/p/11011699.html