题解：P6202 [USACO07CHN] Summing Sums G

wangboyue_740325 · 2026-03-07 20:40:01 · 题解

思路

通项公式：C_i^{(T)} = C_i^{(0)}(-1)^T + \frac{S_0}{N}((N-1)^T - (-1)^T)。通过快速幂计算指数项，费马小定理求逆元，即可直接代入公式求解，时间复杂度为 O(N + \log T)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=98765431,N=5e4+5;
int c[N];
int fpow(int a,int b){
    int ans=1;
    a%=mod;
    while(b>0){
        if(b%2==1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
}
int inv(int n){
    return fpow(n,mod-2);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,t,sum=0;
    cin>>n>>t;
    for(int i=1;i<=n;++i){
        cin>>c[i];
        sum=(sum+c[i])%mod;
    }
    int f=(t%2==0)?1:(mod-1),tot=((sum*inv(n))%mod*(fpow(n-1,t)-f+mod)%mod)%mod;
    for(int i=1;i<=n;++i){
        cout<<((f*c[i])%mod+tot)%mod<<"\n";
    }
    return 0;
}