BZOJ 2614 梦的困境 题解

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2614

首先我们注意到,对于两个数\(i\)和\(j\),如果\(gcd(i,k)=gcd(j,k)\),那么\(i\)和\(j\)是等价的。所以我们先预处理出所有k的约数(经打表发现不超过200个约数),然后将所有给出的数\(i\)按\(gcd(i,k)\)分类。

定义\(val[i][j]=\)第\(i\)个箱子里满足\(gcd(num,k)=j\)的\(num\)个数(\(num\)是输入的那些数)。

再定义\(f[i][j]=\)第\(i\)个箱子中按照题目要求选数,使得选择出来的数的乘积\(mul\)满足\(gcd(mul,k)=j\)的方案数。

怎么得到这个数组呢?

考虑只选择一个数的情况,那么\(f[i][j]=val[i][j]\)

以下所说的\(u\)和\(v\)均为分类过后的\(u\)和\(v\)(即与\(k\)的\(gcd\)为\(u\)和\(v\))

再考虑选择两个数的情况,假如我们选择的两个数是\(u\)和\(v\ (u,v|k)\),那么\(f[i][gcd(u*v,k)]+=val[i][u]*val[i][v]\)

最后再定义\(dp[i][j]=\)前\(i\)个箱子中,按照题目要求选数,使得选择出来的数的乘积\(mul\)满足\(gcd(mul,k)=j\)的方案数

怎么得到这个数组呢?

假如前\(i\)个箱子中,选择的数的乘积是\(u\),在第\(i+1\)个箱子中选择出的数的乘积是\(v\ (u,v|k)\),那么有\(dp[i+1][gcd(u*v,k)]+=dp[i][u]*f[i+1][v]\)

具体实现上,我们需要将约数离散化以减少空间复杂度

#include<cstdio>
#include<cstring>
#include<cmath>
#define int LL
typedef long long LL;
const int MAXN = 200 + 5;
const int MAXM = 10000 + 5;
const int MAXK = 200 + 5;

int val[MAXN][MAXK];
int f[MAXN][MAXK];
int dp[MAXN][MAXK];
int n, m, K, MOD;
int hash[200005], cnt = 0;
int divs[MAXK];

void find_divisior() {
	memset(hash, -1, sizeof hash);
	for(int i = 1; i <= K; ++i) if(K % i == 0)
		hash[i] = cnt, divs[cnt++] = i;
}

LL gcd(LL a, LL b) {
	return b ? gcd(b, a % b) : a;
}
#undef int
int main() {
	scanf("%lld%lld%lld%lld", &n, &m, &K, &MOD);
	find_divisior();
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j) {
			int t;
			scanf("%d", &t);
			val[i][hash[gcd(K, t)]]++;
		}
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < cnt; ++j) f[i][j] = val[i][j];
	for(int i = 1; i < n - 1; ++i)
		for(int j = 0; j < cnt; ++j)
			for(int k = j; k < cnt; ++k) {
				int t = hash[gcd(divs[j] * divs[k], K)];
				if(j == k) f[i][t] += val[i][j] * (val[i][j] - 1);
				else f[i][t] += val[i][j] * val[i][k] * 2;
				f[i][t] %= MOD;
			}
	for(int i = 0; i < cnt; ++i) dp[0][i] = val[0][i];
	for(int i = 0; i < n - 1; ++i)
		for(int j = 0; j < cnt; ++j)
			for(int k = 0; k < cnt; ++k) {
				int t = hash[gcd(divs[j] * divs[k], K)];
				dp[i + 1][t] += (dp[i][j] * f[i + 1][k]);
				dp[i + 1][t] %= MOD;
			}
	printf("%lld\n",dp[n - 1][cnt - 1]);
}

 

发表评论

电子邮件地址不会被公开。