社区讨论

10pts 求hack

P8458 「REOI-p1」打捞参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo8ej4jv
此快照首次捕获于
2023/10/27 17:19
2 年前
此快照最后确认于
2023/10/27 17:19
2 年前
查看原帖
我的思路:
先把待求的两个数列准备好,使得第一个数列比第二个数列短。
在每个最小公共周期中,短数列 c1c1 中的每个元素要与长数列 c2c2 中 间距为 gcdgcd 的所有元素相乘,最后求和。
因此把长数列 c2c2 的隔gcdgcd 项和求出,再与 c1c1 的元素相乘,最后相加得到答案。
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 条回复,欢迎继续交流。

正在加载回复...