P11765 「KFCOI Round #1」回首题目背景控制住不爱一个人很难因为爱是自由意识的沉沦。其实从始至终只要你回首他就永远都陪伴在你身后。题目描述你一共有nnn条重要的回忆每条回忆有一个重要系数kik_iki并且这nnn条回忆彼此之间有mmm个前后关系。每一条关系u,v(1≤u,v≤n)u,v(1\le u,v\le n)u,v(1≤u,v≤n)表示uuu发生的时间恰好在vvv前。可能是因为时间过久导致你的记忆错乱在时间线中可能会出现环。一开始所有点的重要度均为000一共你会进行TTT次回想操作。若当前正在进行第ttt次操作操作前对于一条回忆xix_ixi它的重要度会乘上重要系数kik_iki。操作中对于一条回忆xix_ixi如果有恰好发生在回忆xix_ixi前的回忆yiy_iyi那么将回忆xix_ixi的重要度增加yiy_iyi在本次乘上重要系数kik_iki之前的重要度。否则回忆xix_ixi的重要度增加ttt。当然为了防止一条回忆过于重要输出每条回忆的重要度对998244353998244353998244353取余的结果。形式化题意给定一个nnn个节点mmm条边的有向图并保证不会出现重边。初始所有点的点权都为000。一共将进行TTT次操作。对于第ttt次操作首先将所有点的点权乘上一个给定的值kik_iki。接下来对于一个点xix_ixi如果有连向它的点yiy_iyi那么将xix_ixi的权值加上yiy_iyi在本次乘上kik_iki之前的权值。否则如果没有连向它的点xix_ixi的权值加上ttt。输出的所有点的权值对998244353998244353998244353取余的结果。输入格式本题输入均为正整数。第一行三个数n,m,Tn,m,Tn,m,T表示一共有nnn条回忆mmm个关系以及一共进行TTT次回想操作。第二行nnn个数表示重要系数kik_iki。接下来mmm行每行两个数xi,yix_i,y_ixi,yi表示xix_ixi发生的时间恰好先于yiy_iyi。输出格式输出共一行nnn个数第iii个数表示第iii个点的重要度对998244353998244353998244353取余的结果。输入输出样例 #1输入 #15 5 3 1 2 3 4 5 1 2 2 3 1 4 2 4 4 5输出 #16 5 1 8 1说明/提示样例解释 1第一次操作时所有的点重要度为000。乘上重要系数后依旧为000。第一个点的重要度加上当前正在进行的回想操作次数111。其余点均加上000。第一次操作后所有点的重要度分别为1,0,0,0,0。类似的第二次操作后所有点的重要度分别为3,1,0,1,0。第三次操作后所有点的重要度分别为6,5,1,8,1。数据范围本题采用捆绑测试。Subtask 120 points1≤n≤101\le n \le 101≤n≤101≤T≤101\le T \le 101≤T≤10。Subtask 220 points1≤T≤1051\le T\le 10^51≤T≤105。Subtask 360 points无特殊限制。对于所有测试数据1≤n≤1001\le n\le1001≤n≤1001≤m≤3001\le m\le3001≤m≤3001≤T≤10181\le T\le10^{18}1≤T≤10181≤ki≤1091\le k_i\le10^91≤ki≤1091≤xi,yi≤n1\le x_i,y_i\le n1≤xi,yi≤n。C实现#includebits/stdc.husingnamespacestd;typedeflonglongljl;constljl Mod998244353;constintN105,M305;intn,m,cnt_e,ehead[N],deg[N];ljl T,k[N],g[N][N];boolccc[N];structMTX{ljl v[N][N];MTX(into){memset(v,0,sizeof(v));for(inti1;iN;i)v[i][i]o;}}bs(1),f(0),fac(0);MTXoperator*(MTX a,MTX b){MTXans(0);for(inti1;in2;i)for(intj1;jn2;j)for(intk1;kn2;k)ans.v[i][j](ans.v[i][j]a.v[i][k]*b.v[k][j]%Mod)%Mod;returnans;}MTXqpow(MTX a,ljl k){MTXans(1);while(k){if(k1)ansans*a;aa*a;k1;}returnans;}voidprintfac(){for(inti1;in2;i){for(intj1;jn2;j)coutfac.v[i][j] ;cout\n;}return;}voidoutf(){for(inti1;in;i)coutf.v[1][i] ;cout\n;return;}intmain(){ios::sync_with_stdio(0);cinnmT;for(inti1;in;i)cink[i];for(inti1,u,v;im;i){cinuv;g[u][v]1;ccc[v]1;}for(inti1;in;i)fac.v[i][i]k[i];for(inti1;in;i)for(intj1;jn;j)if(i!j)fac.v[i][j]g[i][j];fac.v[n2][n2]1;fac.v[n2][n1]1;fac.v[n1][n1]1;for(inti1;in;i)fac.v[n1][i](ccc[i]^1);f.v[1][n2]1;f.v[1][n1]1;facqpow(fac,T);ff*fac;outf();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容