题目描述

Description

那N只可爱的奶牛刚刚学习了有关密码的许多算法，终于，她们创造出了属于奶牛的加密方法．由于她们并不是经验十足，她们的加密方法非常简单：第i只奶牛掌握着密码的第i个数字，起始的时候是Ci(0≤Ci < 90000000).加密的时候，第i只奶牛会计算其他所有奶牛的数字和，并将这个数字和除以98765431取余．在所有奶牛计算完毕之后，每一只奶牛会用自己算得的数字代替原有的数字．也就是说，

这样，她们就完成了一次加密． 在十一月，奶牛们把这个加密法则告诉了驼鹿卡门，卡门惊呆了．之后，在一个浓雾弥漫的平安夜，卡门与奶牛们：“你们的算法十分原始，很容易就被人破解．所以你们要重复这个加密过程T(1≤T≤1414213562)次，才能达到加密效果．” 这回轮到奶牛们惊呆了．很显然，奶牛们特别讨厌做同样的无聊的事情很多次．经过了漫长的争论，卡门和奶牛们终于找到的解决办法：你被刚来加密这些数字．

Input

第1行输入N和T，之后N行每行一个整数表示初始的Ci．

Output

共N行，每行一个整数，表示T次加密之后的Ci．

Sample Input

3 4
1
0
4

Sample Output

26
25
29

题目分析

手推几项 发现C[i]能O(1)推出来
听说可以矩阵乘法？

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std; 
long long n;
long long c[500100],sum,t;
long long mod=98765431;
long long ksm(long long x,long long y)
{
    x%=mod;
    long long tmp=1;
    while(y)
    {
        if(y&1ll) tmp=(tmp*x)%mod;
        y>>=1,x=(x*x)%mod;
    }
    return tmp;
}
long long calc(long long a,long long q,long long num)
{ return (ksm(q,num)%mod*(a%mod)%mod-a+mod)%mod*ksm((q-1),mod-2)%mod; }
int main()
{   
    scanf("%lld%lld",&n,&t);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]),sum=(sum+c[i])%mod;
    for(int i=1;i<=n;i++)
    {
        long long tmp;
        if(t==1)
        {
            printf("%lld\n",(sum-c[i]+mod)%mod);
            continue;
        }
        if((t-1)&1ll)
            tmp=((( c[i]%mod+calc( (n-1)*sum , (n-1)*(n-1) , t/2 )%mod)%mod-(calc( sum , (n-1)*(n-1), t/2 ) )%mod)+mod)%mod;
        else
            tmp=((( calc( sum , (n-1)*(n-1) , t/2+1 )%mod-c[i]+mod)%mod-(calc( (n-1)*sum , (n-1)*(n-1) , t/2) )%mod)+mod)%mod ;
        printf("%lld\n",(tmp%mod+mod)%mod);
    }
    return 0;
}