首页 > 代码库 > 【UOJ#129】 【NOI2015】寿司晚宴
【UOJ#129】 【NOI2015】寿司晚宴
题目描述
为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。
在晚宴上，主办方为大家提供了 n−1 种不同的寿司，编号 1,2,3,…,n−1，其中第 i 种寿司的美味度为 i+1 （即寿司的美味度为从 2 到 n）。
现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 x 的寿司，小 W 品尝的寿司中存在一种美味度为 y 的寿司，而 x 与 y 不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 p 取模）。注意一个人可以不吃任何寿司。
输入格式
输入文件的第 1 行包含 2 个正整数 n,p，中间用单个空格隔开，表示共有 n 种寿司，最终和谐的方案数要对 p 取模。
输出格式
输出一行包含 1 个整数，表示所求的方案模 p 的结果。
题解
注意到所有和谐的方案，两人的质数集合一定是不相交的。
对于所有大于根号的质数，不存在一个数同时包含两个这样的数。打个比方，假如n是100，那么我们在考虑17的时候，就不需要考虑11,13有没有取。而小于根号的质数就不具备有这个性质。所以对于大于根号的质数是一个分层的关系，层与层之间是无后效性的，所以我们可以分层来DP。
计f[i][A][B]表示在第i层里一个人集合为A，另一个人集合为B的方案。然后枚举子集、前缀和转移一下就好了。
代码
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 5 #define R register 6 #define maxn 510 7 int pr[maxn], prcnt, mp[maxn], r[maxn]; 8 int f[maxn][256][256][2], g[maxn][256][256], tf[256][256][2]; 9 bool vis[maxn];10 inline bool cmp(R int a, R int b)11 {12 return mp[a] < mp[b];13 }14 int main()15 {16 R int n, p; scanf("%d%d", &n, &p);17 for (R int i = 2; i <= n; ++i)18 {19 r[i] = i;20 if (!vis[i]) pr[++prcnt] = mp[i] = i;21 for (R int j = 1; j <= prcnt && i * pr[j] <= n; ++j)22 {23 vis[i * pr[j]] = 1;24 mp[i * pr[j]] = mp[i];25 if (i % pr[j] == 0) break;26 }27 }28 std::sort(r + 2, r + n + 1, cmp);29 R int tot = 0;30 g[0][0][0] = 1 % p;31 for (R int i = 2; i <= n; ++i)32 {33 R int x = r[i], tS = 0;34 if (mp[x] < 20 || mp[r[i]] != mp[r[i - 1]]) ++tot;35 // printf("%d %d %d %d\n", i, r[i], mp[r[i]], tot);36 for (R int j = 1; j <= prcnt && pr[j] < 20; ++j)37 if (x % pr[j] == 0) tS |= 1 << (j - 1);38 39 memcpy(tf, f[tot], sizeof (tf));40 for (R int A = 0; A < 256; ++A)41 {42 R int mB = ~A & 255;43 for (R int B = mB; B; B = (B - 1) & mB)44 if (!(B & tS))45 (f[tot][A | tS][B][0] += (g[tot - 1][A][B] + tf[A][B][0]) % p) %= p,46 (f[tot][B][A | tS][1] += (g[tot - 1][B][A] + tf[B][A][1]) % p) %= p;47 (f[tot][A | tS][0][0] += (g[tot - 1][A][0] + tf[A][0][0]) % p) %= p;48 (f[tot][0][A | tS][1] += (g[tot - 1][0][A] + tf[0][A][1]) % p) %= p;49 }50 51 for (R int A = 0; A < 256; ++A)52 {53 R int mB = ~A & 255;54 for (R int B = mB; B; B = (B - 1) & mB)55 g[tot][A][B] = (g[tot - 1][A][B] + (f[tot][A][B][0] + f[tot][A][B][1]) % p) % p;56 g[tot][A][0] = (g[tot - 1][A][0] + (f[tot][A][0][0] + f[tot][A][0][1]) % p) % p;57 }58 }59 R int ans = 0;60 for (R int A = 0; A < 256; ++A)61 {62 R int mB = ~A & 255;63 for (R int B = mB; B; B = (B - 1) & mB)64 (ans += g[tot][A][B]) %= p;65 (ans += g[tot][A][0]) %= p;66 }67 printf("%d\n", ans);68 return 0;69 }
【UOJ#129】 【NOI2015】寿司晚宴
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。