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_j'ai′,aj′，则g ( i , j ) = ∑ p = 1 k a i , p ′ × a j , p ′ g(i,j)= \sum\limits_{p=1}^k a'_{i,p}\times a'_{j,p}g(i,j)=p=1∑kai,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}lik遍得到{ 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_{i=1,j=i+1}^{i,j\leq n}\{g(i,j)\bmod 998244353\}i=1,j=i+1maxi,j≤n{g(i,j)mod998244353}，其中g ( i , j ) = ∑ p = 1 k a i , p ′ × a j , p ′ g(i,j)= \sum\limits_{p=1}^k a'_{i,p}\times a'_{j,p}g(i,j)=p=1∑kai,p′×aj,p′。
输入格式
第一行两个整数n nn，k kk。
接下来输入n nn行。第i + 1 i + 1i+1行第一个数为l i l_ili，接下来输入l i l_ili个数，表示打捞者的宝藏a i a_iai。
输出格式
一个整数，表示所求的最大值。
输入输出样例 #1
输入 #1
2 12 3 2 3 4 4 1 2 3 4输出 #1
90输入输出样例 #2
输入 #2
3 999999924 4 4 4 5 3 7 1 9 1 9 8 1 0 6 1 1 4 5 1 4输出 #2
599517664说明/提示
样例解释KaTeX parse error: Expected 'EOF', got '#' at position 1: #̲1
a 1 ′ = 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 a_1'=2, 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_2'=1, 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\times1+3\times2+4\times3+2\times4+3\times1+4\times2+2\times3+3\times4+4\times1+2\times2+3\times3+4\times4=90g(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。
样例解释KaTeX parse error: Expected 'EOF', got '#' at position 1: #̲2
g ( 1 , 2 ) m o d 998244353 = 599517664 g(1,2)\bmod998244353=599517664g(1,2)mod998244353=599517664。
g ( 1 , 3 ) m o d 998244353 = 350889018 g(1,3)\bmod998244353=350889018g(1,3)mod998244353=350889018。
g ( 2 , 3 ) m o d 998244353 = 66930325 g(2,3)\bmod998244353=66930325g(2,3)mod998244353=66930325。
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≤i<j≤nmax{g(i,j)mod998244353}=599517664。
数据范围
对于10 % 10\%10%的数据，有n = 2 n=2n=2。
对于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≤i<j≤n)，gcd \gcdgcd为最大公约数。
对于100 % 100\%100%的数据，有1 ≤ n ≤ 100 ， 1 ≤ l i ≤ 1000 ， 1 ≤ k , a i , j ≤ 10 9 1\leq n\le 100，1\leq l_i\le 1000，1\leq k,a_{i,j}\le 10^{9}1≤n≤100，1≤li≤1000，1≤k,ai,j≤109且对于任意的i ∈ [ 1 , n ] , l i ∣ k i \in [1,n],l_i\mid ki∈[1,n],li∣k。
C++实现
#include<bits/stdc++.h>#definelcm(x,y)x/__gcd(x,y)*y#definelb(x)(x&-x)#definestrto_stringusingnamespacestd;usingll=longlong;constdoubleEPS=1e-6,PAI=acos(-1.0);constintMAX=1e5+5,mod=1e9+7,MOD=998244353;vector<pair<int,vector<ll>>>q(MAX);intn;ll u,ans=0;voidsolve(){cin>>n>>u;for(inti=0;i<n;i++){intx;cin>>x;vector<ll>a(x);for(intj=0;j<x;j++){cin>>a[j];a[j]%=MOD;}q[i]={x,a};}for(inti=0;i<n;i++)for(intj=i+1;j<n;j++){intli=q[i].first,lj=q[j].first;auto&ai=q[i].second,&aj=q[j].second;ll g=__gcd(li,lj),a=li/g,b=lj/g,d=(li/g)*lj,f=(d?u/d:0),rem=u%d,sum=0,sr=0;for(intk=0;k<g;k++){ll sa=0,sb=0;for(into=0;o<a;o++)sa=(sa+ai[g*o+k])%MOD;for(into=0;o<b;o++)sb=(sb+aj[g*o+k])%MOD;sum=(sum+sa*sb)%MOD;}for(ll k=0;k<rem;k++){intidi=k%li,idj=k%lj;sr=(sr+ai[idi]*aj[idj])%MOD;}ll cur=(((f%MOD)*sum)%MOD+sr)%MOD;if(cur>ans)ans=cur;}cout<<ans<<'\n';}intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);intt=1;while(t--)solve();return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
