打卡信奥刷题（3004）用C++实现信奥题 P6202 [USACO07CHN] Summing Sums G

P6202 [USACO07CHN] Summing Sums G

题目描述

N NN头奶牛（1 ≤ N ≤ 5 × 10 4 1 \leq N \leq 5 \times 10^41≤N≤5×104）刚刚学习了不少密码学知识，终于，她们创造出了属于奶牛的加密方法，由于她们经验不足，她们的加密方法很简单：

第i ii头奶牛掌握着密码的第i ii个数字，起始的时候是C i C_iCi​（0 ≤ C i < 9 × 10 7 0 \leq C_i \lt 9 \times 10^70≤Ci​<9×107）。加密的时候，第i ii头奶牛会计算其他所有奶牛的数字和，并将这个和对98 765 431 98\,765\,43198765431取模。在所有奶牛计算完成后，每头奶牛都会用自己算的数字代替原来的数字。即，

C i ′ = ( ∑ k = 1 N C k − C i ) m o d 98 765 431 C_{i}'=(\sum_{k=1}^NC_k-C_i) \bmod 98\,765\,431Ci′​=(k=1∑N​Ck​−Ci​)mod98765431

这样，她们完成了一次加密。

在十一月，奶牛们把这个加密方法告诉了驼鹿卡门。卡门想了一会后，说：“你们的算法还很原始，为了达到加密效果，你们要重复这个加密过程T TT次（1 ≤ T ≤ 1 414 213 562 1 \leq T \leq 1\,414\,213\,5621≤T≤1414213562）”。

奶牛们很懒，于是就把这个任务交给了你。

输入格式

第一行两个整数N , T N,TN,T。

接下来N NN行，第i ii行一个整数C i C_iCi​。

输出格式

输出N NN行，第i ii行一个整数，代表经过T TT次加密后的C i C_iCi​。

输入输出样例 #1

输入 #1

3 4 1 0 4

输出 #1

26 25 29

说明/提示

每次加密后的C i C_iCi​如下：

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmod=98765431,N=5e4+5;intc[N];intfpow(inta,intb){intans=1;a%=mod;while(b>0){if(b%2==1){ans=(ans*a)%mod;}a=(a*a)%mod;b/=2;}returnans;}intinv(intn){returnfpow(n,mod-2);}signedmain(){ios::sync_with_stdio(false);cin.tie(NULL);intn,t,sum=0;cin>>n>>t;for(inti=1;i<=n;++i){cin>>c[i];sum=(sum+c[i])%mod;}intf=(t%2==0)?1:(mod-1),tot=((sum*inv(n))%mod*(fpow(n-1,t)-f+mod)%mod)%mod;for(inti=1;i<=n;++i){cout<<((f*c[i])%mod+tot)%mod<<"\n";}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容