50pts 求hack
查看原帖
50pts 求hack
358971
朦胧_XY楼主2022/8/4 11:57
#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) 得到 两序列的贡献值。

2022/8/4 11:57
加载中...