#include<iostream>
#include<algorithm>
#define ll long long
#define N 205
#define L 1005
#define Mod 998244353
using namespace std;
ll n, k, l[L], a[N][L], fac[L][N], sum[N][N][L], tot[L], vis[L], cnt, ans;
ll tmin, tmax, tj, flag, th, minb, idmin, idmax;
void add(int x, int y, int z){
for(ll i = 1; i <= x; i++){
for(ll p = 1; p <= fac[x][y]; p++){
if(p > i) break;
if((i - p) % fac[x][y] == 0){
sum[z][y][p] += a[z][i];
}
}
}
}
int main(){
scanf("%lld%lld", &n, &k);
for(ll i = 1; i <= n; i++){
scanf("%lld", &l[i]);
for(ll p = 1; p <= l[i]; p++){
scanf("%lld", &a[i][p]);
}
if(!vis[l[i]]){
vis[l[i]] = 1;
for(ll j = 1; j <= l[i]; j++){
if(l[i] % j == 0){
fac[l[i]][++tot[l[i]]] = j;
}
}
}
}
for(int i = 1; i < n; i++){
for(int q = i + 1; q <= n; q++){
flag = 0, th = 0;
if(l[i] <= l[q]){
tmin = l[i], tmax = l[q];
idmin = i, idmax = q;
}
else{
tmin = l[q], tmax = l[i];
idmin = q, idmax = i;
}
for(ll j = tot[tmin]; j >= 1; j--){
for(ll h = tot[tmax]; h >= 1; h--){
if(fac[tmin][j] == fac[tmax][h]){
tj = j, th = h, flag = 1;
break;
}
}
if(flag) break;
}
if(idmin == i && !sum[i][tj][1]) add(tmin, tj, i);
else if(idmax == i && !sum[i][th][1]) add(tmax, th, i);
if(idmin == q && !sum[q][tj][1]) add(tmin, tj, q);
else if(idmax == q && !sum[q][th][1]) add(tmax, th, q);
cnt = 0, minb = (tmin * tmax) / fac[tmin][tj];
for(ll p = 1; p <= fac[tmin][tj]; p++){
cnt += sum[idmin][tj][p] * sum[idmax][th][p];
cnt %= Mod;
}
cnt *= (k / minb), cnt %= Mod;
ans = max(ans, cnt);
}
}
printf("%lld", ans);
return 0;
}
思路:
求两个序列的长度的最大公约数,
再隔着最大公约数将两个序列分别求和,
再将所得数乘以(k/两序列长的最小公倍数)。
例:
两个序列:1 2 3 4 和 1 2 3 4 5 6
长度的最大公约数是2,最小公倍数是12,
就先将 1,3的和 乘以 1,3,5的和,
再加上 2,4的和 乘以 2,4,6的和,
最后将 所得数 乘以(k/12) 得到 两序列的贡献值。