BZOJ-1712: [Usaco2007 China]Summing Sums 加密

Description

加密方法非常简单：第i只奶牛掌握着密码的第i个数字，起始的时候是Ci(0≤Ci< 90000000)加密的时候，第i只奶牛会计算其他所有奶牛的数字和，并将这个数字和除以98765431取余．在所有奶牛计算完毕之后，每一只奶牛会用自己算得的数字代替原有的数字．也就是说，
重复这个加密过程T(1≤T≤1414213562)次

发现c的和可以直接表示，直接推出来公式计算就好了。好像还可以矩乘什么的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=98765431;
ll sum,T;
int n,c[51000];


ll Pow(ll x,ll y)
{
    y%=(mod-1); ll re=1;
    while(y)
    {
        if(y&1) re=re*x%mod;
        x=x*x%mod; y>>=1;
    }
    return re;
}

int main()
{
    scanf("%d%lld",&n,&T);
    for(int i=1;i<=n;++i) scanf("%d",c+i),sum=(sum+c[i])%mod;
    ll tmp=Pow(n-1,T);
    if(T&1) tmp++; else tmp--;
    tmp%=mod; tmp=tmp*sum%mod; tmp=tmp*Pow(n,mod-2)%mod;
    for(int i=1;i<=n;++i)
    {
        if(T&1) printf("%lld\n",(tmp-c[i]+mod)%mod);
        else printf("%lld\n",(tmp+c[i])%mod);
    }
    return 0;
}