P8458 「REOI-p1」打捞题目背景出题人XL4453验题人犇犇犇犇文案小糯米upd注意先取模再取max题目描述“别介意我和那些家伙都是打捞者。我们在头一次追寻梦想降落到地表时就做好丧命的准备和赴死的觉悟了。”葛力克一行人在一次打捞中时来运转获得了不少的宝藏。在归途之路言及谁的功劳最大之时大家却起了冲突。有人说自己的宝藏是史上绝无仅有是在鬼门关前绕了一大圈才好不容易抢到的一个有人说自己惨淡经营虽然没有获得那么珍贵的宝物但数量可观也足以与之相提并论也有人说自己的收获二者兼有应当综合评价云云总之场面一片混乱颇有生死与共的患难之交从此决裂的危险。于是大家把目光投到了葛力克的身上这让他十分为难。思索良久他决定这样来评价大家的贡献假设一共有n nn名打捞者第i ii位打捞者a i a_iai​取得的宝物数量为l i l_ili​而其中第p pp件宝物对应的价值则为a i , p a_{i,p}ai,p​那么在计算的时候只需要将每个序列相加求和即可。但是葛力克并不满足于现状他现在想知道如果是将两个人的贡献放在一起看待那么又将如何计算呢一番激烈的头脑风暴后他决定这样来计算两位打捞者i , j i,ji,j之间的贡献g ( i , j ) g(i,j)g(i,j)将a i a_iai​与a j a_jaj​分别复制数遍使得两堆宝物的数量都为k kk得到两个序列a i ′ , a j ′ a_i,a_jai′​,aj′​则g ( i , j ) ∑ p 1 k a i , p ′ × a j , p ′ g(i,j) \sum\limits_{p1}^k a_{i,p}\times a_{j,p}g(i,j)p1∑k​ai,p′​×aj,p′​。现在葛力克想知道这个贡献值的最大值是多少。因为贡献值可能会很大超出了正常生物大脑的运算能力所以我们对它进行998244353 998244353998244353的取余。形式化题面给定一个整数n nn和n nn个序列第i ii个序列{ a i } \{a_i\}{ai​}长度为l i l_ili​将每个a i a_iai​复制k l i \dfrac k{l_i}li​k​遍得到{ a i ′ } \{a_i\}{ai′​}使得{ a i ′ } \{a_i\}{ai′​}的长度为k kk。试求max ⁡ i 1 , j i 1 i , j ≤ n { g ( i , j ) m o d 998244353 } \max\limits_{i1,ji1}^{i,j\leq n}\{g(i,j)\bmod 998244353\}i1,ji1maxi,j≤n​{g(i,j)mod998244353}其中g ( i , j ) ∑ p 1 k a i , p ′ × a j , p ′ g(i,j) \sum\limits_{p1}^k a_{i,p}\times a_{j,p}g(i,j)p1∑k​ai,p′​×aj,p′​。输入格式第一行两个整数n nnk kk。接下来输入n nn行。第i 1 i 1i1行第一个数为l i l_ili​接下来输入l i l_ili​个数表示打捞者的宝藏a i a_iai​。输出格式一个整数表示所求的最大值。输入输出样例 #1输入 #12 12 3 2 3 4 4 1 2 3 4输出 #190输入输出样例 #2输入 #23 999999924 4 4 4 5 3 7 1 9 1 9 8 1 0 6 1 1 4 5 1 4输出 #2599517664说明/提示样例解释KaTeX parse error: Expected EOF, got # at position 1: #̲1a 1 ′ 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 a_12, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3, 4a1′​2,3,4,2,3,4,2,3,4,2,3,4。a 2 ′ 1 , 2 , 3 , 4 , 1 , 2 , 3 , 4 , 1 , 2 , 3 , 4 a_21, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4a2′​1,2,3,4,1,2,3,4,1,2,3,4。g ( 1 , 2 ) 2 × 1 3 × 2 4 × 3 2 × 4 3 × 1 4 × 2 2 × 3 3 × 4 4 × 1 2 × 2 3 × 3 4 × 4 90 g(1,2)2\times13\times24\times32\times43\times14\times22\times33\times44\times12\times23\times34\times490g(1,2)2×13×24×32×43×14×22×33×44×12×23×34×490。样例解释KaTeX parse error: Expected EOF, got # at position 1: #̲2g ( 1 , 2 ) m o d 998244353 599517664 g(1,2)\bmod998244353599517664g(1,2)mod998244353599517664。g ( 1 , 3 ) m o d 998244353 350889018 g(1,3)\bmod998244353350889018g(1,3)mod998244353350889018。g ( 2 , 3 ) m o d 998244353 66930325 g(2,3)\bmod99824435366930325g(2,3)mod99824435366930325。max ⁡ 1 ≤ i j ≤ n { g ( i , j ) m o d 998244353 } 599517664 \max\limits_{1\leq i j \leq n}\{g(i,j)\bmod998244353\}5995176641≤ij≤nmax​{g(i,j)mod998244353}599517664。数据范围对于10 % 10\%10%的数据有n 2 n2n2。对于30 % 30\%30%的数据有k ≤ 100 k \leq 100k≤100。对于60 % 60\%60%的数据所有l i l_ili​两两互质即gcd ⁡ ( l i , l j ) 1 ( 1 ≤ i j ≤ n ) \gcd(l_i,l_j)1(1\leq i j \leq n)gcd(li​,lj​)1(1≤ij≤n)gcd ⁡ \gcdgcd为最大公约数。对于100 % 100\%100%的数据有1 ≤ n ≤ 100 1 ≤ l i ≤ 1000 1 ≤ k , a i , j ≤ 10 9 1\leq n\le 1001\leq l_i\le 10001\leq k,a_{i,j}\le 10^{9}1≤n≤1001≤li​≤10001≤k,ai,j​≤109且对于任意的i ∈ [ 1 , n ] , l i ∣ k i \in [1,n],l_i\mid ki∈[1,n],li​∣k。C实现#includebits/stdc.h#definelcm(x,y)x/__gcd(x,y)*y#definelb(x)(x-x)#definestrto_stringusingnamespacestd;usinglllonglong;constdoubleEPS1e-6,PAIacos(-1.0);constintMAX1e55,mod1e97,MOD998244353;vectorpairint,vectorllq(MAX);intn;ll u,ans0;voidsolve(){cinnu;for(inti0;in;i){intx;cinx;vectorlla(x);for(intj0;jx;j){cina[j];a[j]%MOD;}q[i]{x,a};}for(inti0;in;i)for(intji1;jn;j){intliq[i].first,ljq[j].first;autoaiq[i].second,ajq[j].second;ll g__gcd(li,lj),ali/g,blj/g,d(li/g)*lj,f(d?u/d:0),remu%d,sum0,sr0;for(intk0;kg;k){ll sa0,sb0;for(into0;oa;o)sa(saai[g*ok])%MOD;for(into0;ob;o)sb(sbaj[g*ok])%MOD;sum(sumsa*sb)%MOD;}for(ll k0;krem;k){intidik%li,idjk%lj;sr(srai[idi]*aj[idj])%MOD;}ll cur(((f%MOD)*sum)%MODsr)%MOD;if(curans)anscur;}coutans\n;}intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);intt1;while(t--)solve();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容