今年NOI确实是在下输了。最近想把当时不会做的题都写一下。
题意
从2到n(500)这些数字中,选若干分给A,若干分给B,满足不存在:A的某个数和B的某个数的GCD不等于1。
对于寿司晚宴这题,标准解答确实是有个神奇的DP。
算法
我们要关注的只是所有的质数。最简单的想法就是枚举A,B各获得哪些数。但是质数的数量实在比较多。然后有个技巧就是将小于\(\sqrt n\)的质数和大于\(\sqrt n\)的数分开处理。这样做的原因是一个数最多只能有一个大于\(\sqrt n\)的质因数。
这样的话,小于\(\sqrt n\)的质数就只有8个了。状态压缩DP或者容斥,就能在\(O(2^8 \times 2^8 n)\)内计算出,A获得的质数集合是x(状态压缩为一整数),B获得的质数集合是y时,有多少种方案,记为f(x, y)。注意,这里的方案并没有计算含有大于\(\sqrt n\)的质因数的数字。
接下来,我们要把这些数字也算入答案。奇妙的DP就在这里体现了。
我们只要枚举大于\(\sqrt n\)的那些质数p,一个一个累加到f里,就可以得到最终的答案了。
设g(i, x, y)表示将\(ip\)这个数字分出去后(或者不分给任何人),A获得的质数集合是x,B获得的质数集合是y的方案数。那么,考虑下一个数\((i+1)p\),分给A(分给B同理):
\[g(i + 1, add(x, (i+1)p), y) = g(i, x, y) + f(x, y)
\]
\]
add(x, num)
表示将num这个数加进去后,x的变化。
我可能说得不是很清楚,但这毕竟我是打算自己看的。
代码
#include <bits/stdc++.h>
using namespace std;
int n, MOD;
const int prime[] = {2, 3, 5, 7, 11, 13, 17, 19};
void clear(int (*array)[256]) {
memset(array, 0, sizeof(int) * 256 * 256);
}
void copy(int (*src)[256], int (*dest)[256]) {
memcpy(dest, src, sizeof(int) * 256 * 256);
}
void add(int &x, int delta) {
if (delta >= MOD) delta -= MOD;
x += delta;
if (x >= MOD) x -= MOD;
}
int main() {
scanf("%d%d", &n, &MOD);
static int devide[503];
for (int j = 1; j <= n; j++) {
int ret = 0;
int num = j;
for (int i = 0; i < 8; i++) {
int x = prime[i];
while (num % x == 0) {
num /= x;
ret |= 1 << i;
}
}
if (num == 1) devide[j] = ret;
else devide[j] = ret ? -2 : -1;
}
static int dp[2][256][256];
int (*cur)[256] = dp[0];
int (*next)[256] = dp[1];
cur[0][0] = 1;
for (int i = 2; i <= n; i++) {
int s = devide[i];
if (s < 0) continue;
copy(cur, next);
for (int a = 0; a < 256; a++)
for (int b = 0; b < 256; b++) {
int &x = cur[a][b];
if (x) {
if (! (s & b)) add(next[a | s][b], x);
if (! (s & a)) add(next[a][b | s], x);
}
}
swap(next, cur);
}
static int f[256][256];
for (int i = 23; i <= n; i++) {
if (devide[i] != -1) continue;
clear(f);
for (int j = 1; j * i <= n; j++) {
int s = devide[j];
for (int a = 255; a >= 0; a--)
for (int b = 255; b >= 0; b--) {
if (! (s & b)) add(f[a | s][b], f[a][b] + cur[a][b]);
}
}
for (int a = 0; a < 256; a++)
for (int b = 0; b < 256; b++)
add(cur[a][b], f[a][b] + f[b][a]);
}
int ans = 0;
for (int a = 0; a < 256; a++)
for (int b = 0; b < 256; b++)
add(ans, cur[a][b]);
printf("%d\n", ans);
return 0;
}