洛谷P2150 寿司晚宴
2024-10-12 14:40:14
解：发现每个质数只能属于一个人，于是想到每个质数有三种情况：属于a，属于b，都不属于。
然后考虑状压每个人的质数集合，可以得到30分。
转移就是外层枚举每个数，内层枚举每个人的状态，然后看能否转移。能转移就转移。
考虑优化：有个套路是大于√的质数最多只有一个。于是单独考虑那些，先把不含那些的转移出来放到数组f中。
然后每次外层枚举一个质数，中层枚举它的倍数，内层枚举两个人的状态。
每个质数可以属于a或者属于b或者都不属于。考虑到转移属于a的时候我们不可避免的会算到都不属于(除非再开一维记录)，于是容斥一波。
属于a和属于b因为要分开转移多次(中层枚举倍数)，于是用g，h数组分别转移。
最后f = g + h - f(容斥掉都不属于)。
其实感觉多开一维好想一点......。
#include <bits/stdc++.h> typedef long long LL;
const int N = , M = ; int n, sta[N], p[N], top, last[N], id[N], stk[N], tp;
LL f[][M][M], g[][M][M], MO, h[][M][M], F[M][M];
bool vis[N]; inline void Add(LL &a, const LL &b) {
a += b;
while(a >= MO) a -= MO;
while(a < ) a += MO;
return;
} inline void getp(int n) {
for(int i = ; i <= n; i++) {
if(!vis[i]) {
p[++top] = i;
id[i] = top;
last[i] = i;
}
for(int j = ; j <= top && i * p[j] <= n; j++) {
vis[i * p[j]] = ;
last[i * p[j]] = p[j];
if(i % p[j] == ) break;
}
}
return;
} int main() { //freopen("in.in", "r", stdin); scanf("%d%lld", &n, &MO);
getp(n); int m = ;
while(m < top && p[m + ] <= ) m++;
int lm = << m; for(int i = ; i <= n; i++) {
int x = i, y;
while(x > ) {
y = last[x];
if(id[y] <= m) sta[i] |= ( << (id[y] - ));
else sta[i] |= ( << m);
while(x % y == ) x /= y;
}
} LL ans = ;
f[][][] = ;
for(int i = ; i <= n; i++) {
memset(f[(i + ) & ], , sizeof(f[]));
if((sta[i] & (lm - )) != sta[i]) {
stk[++tp] = i;
memcpy(f[(i + ) & ], f[i & ], sizeof(f[i & ]));
continue;
}
for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if((s & t) || (!f[i & ][s][t])) continue;
/// f[i][s][t]
Add(f[(i + ) & ][s][t], f[i & ][s][t]);
if((sta[i] & t) == ) {
Add(f[(i + ) & ][s | sta[i]][t], f[i & ][s][t]);
}
if((sta[i] & s) == ) {
Add(f[(i + ) & ][s][t | sta[i]], f[i & ][s][t]);
}
}
}
} for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
Add(F[s][t], f[(n + ) & ][s][t]);
}
} for(int i = ; i <= tp; i++) {
if(vis[stk[i]]) {
continue;
} memcpy(g[], F, sizeof(F));
memcpy(h[], F, sizeof(F));
int time = ;
for(int x = stk[i]; x <= n; x += stk[i], time++) {
memset(g[(time + ) & ], , sizeof(g[]));
memset(h[(time + ) & ], , sizeof(h[])); for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
Add(g[(time + ) & ][s][t], g[time & ][s][t]);
Add(h[(time + ) & ][s][t], h[time & ][s][t]);
if((sta[time] & t) == ) {
Add(g[(time + ) & ][s | sta[time]][t], g[time & ][s][t]);
}
if((sta[time] & s) == ) {
Add(h[(time + ) & ][s][t | sta[time]], h[time & ][s][t]);
}
}
}
}
for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
F[s][t] = -F[s][t];
Add(F[s][t], g[time & ][s][t]);
Add(F[s][t], h[time & ][s][t]);
}
}
} for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
Add(ans, F[s][t]);
}
} printf("%lld\n", ans);
return ;
}
AC代码(容斥)
#include <bits/stdc++.h> typedef long long LL;
const int N = , M = ; int n, sta[N], p[N], top, last[N], id[N], stk[N], tp;
LL f[][M][M], g[][M][M][], MO, h[][M][M][], F[M][M];
bool vis[N]; inline void Add(LL &a, const LL &b) {
a += b;
while(a >= MO) a -= MO;
while(a < ) a += MO;
return;
} inline void getp(int n) {
for(int i = ; i <= n; i++) {
if(!vis[i]) {
p[++top] = i;
id[i] = top;
last[i] = i;
}
for(int j = ; j <= top && i * p[j] <= n; j++) {
vis[i * p[j]] = ;
last[i * p[j]] = p[j];
if(i % p[j] == ) break;
}
}
return;
} int main() { //freopen("in.in", "r", stdin); scanf("%d%lld", &n, &MO);
getp(n); int m = ;
while(m < top && p[m + ] <= ) m++;
int lm = << m; for(int i = ; i <= n; i++) {
int x = i, y;
while(x > ) {
y = last[x];
if(id[y] <= m) sta[i] |= ( << (id[y] - ));
else sta[i] |= ( << m);
while(x % y == ) x /= y;
}
} LL ans = ;
f[][][] = ;
for(int i = ; i <= n; i++) {
memset(f[(i + ) & ], , sizeof(f[]));
if((sta[i] & (lm - )) != sta[i]) {
stk[++tp] = i;
memcpy(f[(i + ) & ], f[i & ], sizeof(f[i & ]));
continue;
}
for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if((s & t) || (!f[i & ][s][t])) continue;
/// f[i][s][t]
Add(f[(i + ) & ][s][t], f[i & ][s][t]);
if((sta[i] & t) == ) {
Add(f[(i + ) & ][s | sta[i]][t], f[i & ][s][t]);
}
if((sta[i] & s) == ) {
Add(f[(i + ) & ][s][t | sta[i]], f[i & ][s][t]);
}
}
}
} for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
Add(F[s][t], f[(n + ) & ][s][t]);
}
} for(int i = ; i <= tp; i++) {
if(vis[stk[i]]) {
continue;
} //memcpy(g[1], F, sizeof(F));
//memcpy(h[1], F, sizeof(F));
for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
g[][s][t][] = F[s][t];
g[][s][t][] = ;
h[][s][t][] = F[s][t];
h[][s][t][] = ;
}
} int time = ;
for(int x = stk[i]; x <= n; x += stk[i], time++) {
memset(g[(time + ) & ], , sizeof(g[]));
memset(h[(time + ) & ], , sizeof(h[])); for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
Add(g[(time + ) & ][s][t][], g[time & ][s][t][]);
Add(g[(time + ) & ][s][t][], g[time & ][s][t][]);
Add(h[(time + ) & ][s][t][], h[time & ][s][t][]);
Add(h[(time + ) & ][s][t][], h[time & ][s][t][]);
if((sta[time] & t) == ) {
Add(g[(time + ) & ][s | sta[time]][t][], g[time & ][s][t][]);
Add(g[(time + ) & ][s | sta[time]][t][], g[time & ][s][t][]);
}
if((sta[time] & s) == ) {
Add(h[(time + ) & ][s][t | sta[time]][], h[time & ][s][t][]);
Add(h[(time + ) & ][s][t | sta[time]][], h[time & ][s][t][]);
}
}
}
}
for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
//F[s][t] = -F[s][t];
//F[s][t] = 0;
Add(F[s][t], g[time & ][s][t][]);
Add(F[s][t], h[time & ][s][t][]);
}
}
} for(int s = ; s < lm; s++) {
for(int t = ; t < lm; t++) {
if(s & t) continue;
Add(ans, F[s][t]);
}
} printf("%lld\n", ans);
return ;
}
AC代码(多开一维)
最新文章
- DOS 命令For精解示例
- DBA-mysql-表
- 如何手动修改XP系统属性中的技术支持信息
- SharePoint表单和工作流 - Nintex篇（六）
- 对同一元素设置overflow-x:hidden,overflow-y:visible;属性值不生效
- Source Insight的应用技巧、宏功能
- Android 100多个Styles快速开发布局XML，一行搞定View属性，一键统一配置UI...
- 构建ASP.NET MVC4+EF5+EasyUI+Unity2.x注入的后台管理系统（22）-权限管理系统-模块导航制作
- E - Swap - hdu 2819(简单二分图匹配)
- Python提取图片的ROI
- haproxy 中的http请求和https请求
- Node.js服务端框架谁才是你的真爱
- pig加载两个不同字段个数的文件？load file with different items（f1有42列，f2有43列读到一个对象中）
- Java_Object
- 读javascript高级程序设计-目录
- linux 入门学习
- Docker 从入门到实践（一）Docker 简介
- koa2入门（2） koa-router 路由处理
- Spring学习二
- java 上传图片压缩