P8458 「REOI-p1」打捞

题目背景

出题人：XL4453

验题人：犇犇犇犇

文案：小糯米

upd：注意，先取模再取max

题目描述

“别介意，我和那些家伙都是打捞者。我们在头一次追寻梦想降落到地表时，就做好丧命的准备和赴死的觉悟了。”

葛力克一行人在一次打捞中，时来运转，获得了不少的宝藏。在归途之路，言及谁的功劳最大之时，大家却起了冲突。有人说自己的宝藏是史上绝无仅有，是在鬼门关前绕了一大圈才好不容易抢到的一个；有人说自己惨淡经营，虽然没有获得那么珍贵的宝物，但数量可观，也足以与之相提并论；也有人说自己的收获二者兼有，应当综合评价云云：总之，场面一片混乱，颇有生死与共的患难之交从此决裂的危险。

于是，大家把目光投到了葛力克的身上，这让他十分为难。思索良久，他决定这样来评价大家的贡献：

假设一共有 $n$ 名打捞者，第 $i$ 位打捞者 $a_i$ 取得的宝物数量为 $l_i$ ，而其中第 $p$ 件宝物对应的价值则为 $a_{i,p}$ ，那么在计算的时候只需要将每个序列相加求和即可。但是葛力克并不满足于现状，他现在想知道，如果是将两个人的贡献放在一起看待，那么又将如何计算呢？
一番激烈的头脑风暴后，他决定这样来计算两位打捞者 $i,j$ 之间的贡献 $g(i,j)$ ：将 $a_i$ 与$a_j$ 分别复制数遍使得两堆宝物的数量都为 $k$ ，得到两个序列 $a_i^{\prime },a_j^{\prime }$ ，则 $g(i,j)=\sum _{p=1}^k{a}_{i,p}^{\prime }\times a_{j,p}^{\prime }$ 。

现在葛力克想知道，这个贡献值的最大值是多少。

因为贡献值可能会很大，超出了正常生物大脑的运算能力，所以我们对它进行 $998244353$ 的取余。

---

形式化题面：给定一个整数 $n$，和 $n$ 个序列，第 $i$ 个序列 { a i } \{a_i\} {ai​} 长度为 $l_i$，将每个 $a_i$ 复制 $\frac{k}{l_i}$ 遍得到 { a i ′ } \{a'_i\} {ai′​} 使得 { a i ′ } \{a'_i\} {ai′​} 的长度为 $k$。

试求： 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)=\sum _{p=1}^k{a}_{i,p}^{\prime }\times a_{j,p}^{\prime }$ 。

输入格式

第一行两个整数 $n$，$k$。

接下来输入 $n$ 行。第 $i+1$ 行第一个数为 $l_i$，接下来输入 $l_i$ 个数，表示打捞者的宝藏 $a_i$。

输出格式

一个整数，表示所求的最大值。

输入输出样例 #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^{\prime }=2,3,4,2,3,4,2,3,4,2,3,4$。
$a_2^{\prime }=1,2,3,4,1,2,3,4,1,2,3,4$。
$g(1,2)=2\times 1+3\times 2+4\times 3+2\times 4+3\times 1+4\times 2+2\times 3+3\times 4+4\times 1+2\times 2+3\times 3+4\times 4=90$。

样例解释 KaTeX parse error: Expected 'EOF', got '#' at position 1: #̲2

$g(1,2)\mathrm{mod}998244353=599517664$。
$g(1,3)\mathrm{mod}998244353=350889018$。
$g(2,3)\mathrm{mod}998244353=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\}=599517664 1≤i<j≤nmax​{g(i,j)mod998244353}=599517664。

数据范围

对于 $10\%$ 的数据，有 $n=2$。
对于 $30\%$ 的数据，有 $k\le 100$。
对于 $60\%$ 的数据，所有 $l_i$ 两两互质，即 $\gcd (l_i,l_j)=1(1\le i<j\le n)$，$\gcd$ 为最大公约数。
对于 $100\%$ 的数据，有 $1\le n\le 100，1\le l_i\le 1000，1\le k,a_{i,j}\le 10^9$ 且对于任意的 $i\in [1,n],l_i\mid k$。

C++实现

#include<bits/stdc++.h>
#define lcm(x,y) x/__gcd(x,y)*y
#define lb(x) (x&-x)
#define str to_string
using namespace std;
using ll=long long;
const double EPS=1e-6,PAI=acos(-1.0);
const int MAX=1e5+5,mod=1e9+7,MOD=998244353;
vector<pair<int,vector<ll>>>q(MAX);
int n;
ll u,ans=0;
void solve(){
    cin>>n>>u;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        vector<ll>a(x);
        for(int j=0;j<x;j++){
            cin>>a[j];
            a[j]%=MOD;
        }
        q[i]={x,a};
    }
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
        int li=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(int k=0;k<g;k++){
            ll sa=0,sb=0;
            for(int o=0;o<a;o++)sa=(sa+ai[g*o+k])%MOD;
            for(int o=0;o<b;o++)sb=(sb+aj[g*o+k])%MOD;
            sum=(sum+sa*sb)%MOD;
        }
        for(ll k=0;k<rem;k++){
            int idi=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';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)solve();
    return 0;
}

后续

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