N - 寿司晚宴 HYSBZ - 4197 状压dp
N - 寿司晚宴
这个题目我觉得还是很难的,借助题解写出来的,题解还看了很久,现在还是不是很理解。
首先这个数比较大有500,如果直接就像这个题目S - Query on a tree 这样写就超时了,而且也存不下这么大的数。
因为这个500以内的质数太多了,然后看了这么多题解你会发现根号500以内的质数只有8个。
而每一个数大于根号500的质数最多一个,所以我们可以先讨论这个小于根号500的质数,然后再判断这个大于根号500的质数。
讨论完之后再判断这个大于根号500的质数的问题。
然后发现这个题目可以一起计算这两个。
首先把这个按照大于根号500的这个数进行分块,大于根号500的相同的质数分成一块,只有每一个块的结束才可以更新答案。
这个是因为每一块里面我们第一个人选这个或者第二个人选这个,所以如果你每次都去更新答案就不可以保证只有一个人选择这块的这个质数。
其实本来只要一个f数字f[i][j]表示第一个人的状态为 i 第二个人的状态为 j 的方案数,但是因为我们要保证这一块只有一个人选了这个质数,
意思就是第一个人如果要选这个只能向他选了这个的方向转移,第二个人同理。
怎么确定这个转移方向就是加一维 g[k][i][j] k==0 代表第一个人选了,k==1 代表第二个人选的。
然后之后又不需要分开了,所以又赋值会 f 数组。
差不多就是这样。
总的来说:
1. 既然已知这个是一个状压dp就要去找状压什么,这个和质数有关,所以很明显就是状压质数,根据质因数分解所以可以知道每一个数大于根号x的数最多就一个。
2.状态转移,因为之前写过的那个题目,所以可以知道,首先枚举数,然后枚举状态,这个可以一起枚举这两个人的状态。
3.第二点是不考虑有大于根号500的质数的情况,对于大于根号500 这个需要一个新数组来转移,最后赋值回去。
这个赋值回去之后就表示之后的一个数可以任意选之前的两个状态之间的一个状态,没有冲突。
对于第三点可以这么说,就是在每一块里面我们进行转移,分块的结束我们在重新赋值,之后又分块,但是后面的块可以向前面块中转移。
讲的也不是很清楚,感觉自己还是不是很理解。
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;
typedef long long ll;
ll dp[ << ][ << ], g[][ << ][ << ];
struct node {
ll s, prime;
}a[maxn];
int p[maxn], isp[maxn], m;
void init() {
for (int i = ; i < ; i++) p[i] = ;
for (int i = ; i*i < ; i++) {
if (p[i]) {
for (int j = i * i; j <= ; j += i) {
p[j] = ;
}
}
}
int m = ;
for (int i = ; i <= maxn; i++) if (p[i]) isp[m++] = i;
}
bool cmp(node a, node b) {
return a.prime < b.prime;
}
int main() {
init();
int n, mod;
scanf("%d%d", &n, &mod);
for (int i = ; i < n; i++) {
int x = i + ;
for (int j = ; j < ; j++) {
if (x%isp[j]) continue;
a[i].s |= ( << j);
while (x%isp[j] == ) x /= isp[j];
}
a[i].prime = x;
}
int ends = ( << );
memset(dp, , sizeof(dp));
dp[][] = ;
sort(a + , a + n, cmp);
for (int i = ; i < n; i++) {
if (i == || a[i].prime != a[i - ].prime || a[i].prime == ) {
memcpy(g[], dp, sizeof(dp));
memcpy(g[], dp, sizeof(dp));
}
for (int j = ends - ; j >= ; j--) {
for (int k = ends - ; k >= ; k--) {
if (j&k) continue;
if ((a[i].s&k) == ) (g[][a[i].s | j][k] += g[][j][k]) %= mod;
if ((a[i].s&j) == ) (g[][j][k | a[i].s] += g[][j][k]) %= mod;
}
}
if (i == n - || a[i].prime != a[i + ].prime || a[i].prime == ) {
for (int j = ends - ; j >= ; j--) {
for (int k = ends - ; k >= ; k--) {
if (j&k) continue;
dp[j][k] = (g[][j][k] + g[][j][k] - dp[j][k] + mod) % mod;
}
}
}
}
ll ans = ;
for (int j = ends - ; j >= ; j--) {
for (int k = ends - ; k >= ; k--) {
if (j&k) continue;
ans += dp[j][k];
ans %= mod;
}
}
ans += mod;
printf("%lld\n", ans%mod);
return ;
}
状压 难
最新文章
- 快速上手制作Icon Font
- Docker中自动化搭建Hadoop2.6完全分布式集群
- 发现数据库错误模式(AppScan扫描结果)
- Codeforces Round #116 (Div. 2, ACM-ICPC Rules)
- android 反编译 逆向工具整理
- MongoDB 3 + Windows 7 X64安装及配置
- to_number,Extract oracle的关键字
- console.log的使用
- AD设计中,三种大面积覆铜的区别
- CVPR 2013 录用论文【待更新】
- HDU 2485 Destroying the bus stations (IDA*+ BFS)
- Week9(11月4日)
- Silverlight 中MatrixTransform和其他Transform的数值转换
- bug:逆向思维的延伸
- [国嵌攻略][045-046][一跃进入C大门]
- THINKPHP 调试------输出sql语句
- jfinal afterJFinalStart中执行长久循环操作的解决方案:创建新线程
- Flume集群搭建
- 每天进步一点点-一切皆对象/一次编写,到处运行/bean工厂
- c# word操作
热门文章
- cgdb使用方法
- compareAndSet() 注意点
- Git应用详解第八讲:Git标签、别名与Git gc
- Thinking in Java,Fourth Edition(Java 编程思想,第四版)学习笔记(十三)之Strings
- GitHub 热点速览 Vol.16:化身蒙娜丽莎和乔布斯对话
- K - Two Contests
- ATcoder--D - Summer Vacation
- 基于Lua的游戏服务端框架简介
- JS Math&;Date的方法 (上)
- Python生成一维码