社区讨论
10pts 求hack
P8458 「REOI-p1」打捞参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo8ej4jv
- 此快照首次捕获于
- 2023/10/27 17:19 2 年前
- 此快照最后确认于
- 2023/10/27 17:19 2 年前
我的思路:
先把待求的两个数列准备好,使得第一个数列比第二个数列短。
在每个最小公共周期中,短数列 中的每个元素要与长数列 中 间距为 的所有元素相乘,最后求和。
因此把长数列 的隔 项和求出,再与 的元素相乘,最后相加得到答案。
CPP#include<iostream>
#include<cstdio>
#define M 998244353
using namespace std;
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c<'0' || c>'9'){
if(c == '-') f = -1;
c = getchar();
}
while(c>='0' && c<='9'){
x = (x<<3) + (x<<1) + (c-'0');
c = getchar();
}
return x * f;
}
inline int gcd(int a, int b){
if(b == 0) return a;
if(a < b) swap(a, b);
return gcd(b, a % b);
}
inline int lcm(int a, int b){
return (int)1ll * a * b / gcd(a, b);
}
int n,k,l[200],a[200][1010];
long long ans;
long long work(int x, int y){
int c1[1010] = {}, c2[1010] = {};
if(l[x] > l[y]) swap(x, y);
for(int i = 1; i <= l[x]; i++){
c1[i] = a[x][i];
}
for(int i = 1; i <= l[y]; i++){
c2[i] = a[y][i];
}
int gc = gcd(l[x], l[y]);
int lc = lcm(l[x], l[y]);
long long ans = 0;
for(int i = 1; i <= l[x]; i++){
// tmpÊÇc2µÄ¸ôgcÏîºÍ£¬´Óc2µÄµÚiÏʼ¼ÆËã
long long tmp = 0;
// ÔÚ×îС¹«¹²ÖÜÆÚÖУ¬c1ÖØ¸´ÁË lc / l[x] ´Î
// ËùÒÔtmp×ܹ²Òª¼Ó lc / l[x] Ïî
for(int j = 1; j <= lc / l[x]; j++){
// hÊǽ«Òª¼ÓÈëtmpµÄc2µÄÏîµÄϱê
int h = (i + (j-1) * gc) % l[y];
if(h == 0) h = l[y];
tmp += c2[h];
tmp %= M;
}
ans += c1[i] * tmp % M;
ans %= M;
}
ans *= k / lc;
ans %= M;
return ans;
}
int main(){
n = read(), k = read();
for(int i = 1; i <= n; i++){
l[i] = read();
for(int j = 1; j <= l[i]; j++){
a[i][j] = read();
}
}
ans = -1e9;
for(int i = 1; i <= n-1; i++){
ans = max(ans, work(i, i + 1));
}
cout<<ans;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...