洛谷$P2150\ [NOI2015]$寿司晚宴 $dp$
2024-09-06 15:17:48
正解:$dp$
解题报告:
遇事不决写$dp$($bushi$.讲道理这题一看就感觉除了$dp$也没啥很好的算法能做了,于是考虑$dp$呗
先看部分分?$30pts$发现质因数个数贼少就考虑状压$dp$就完事鸭.
然后现在$100pts$,发现质因数个数太多就$GG$了.
但是这时候考虑显然每个数最多有一个$\geq \sqrt n$的质因数.
所以对质因数以$\sqrt n$为界分为两类,对大于等于$\sqrt n$的质因数$x$直接枚举,显然$x$的倍数只能放在一个集合中或不放,所以直接枚举这个$x$每次分别$dp$再合并起来就好.
具体来说,设$f_{i,j}$表示第一个人选的$\leq \sqrt n$的质因数集合为$i$,第二个选的为$j$的方案数.然后再设$g_{0/1,i,j}$为辅助$dp$数组,即枚举$x$的时候记录$x$的倍数不放到第二个集合/第一个集合的方案数.
然后注意下的是每次$g$转回$f$的时候递推式是$f_{i,j}=g_{0,i,j}+g_{1,i,j}-f_{i,j}$.就,因为两个$g$都会包含所有$x$的倍数都不选的情况,所以就要去重,发现重复的刚好是$f_{i,j}$,减去就好
$over$
嗷注意一个小细节就它是$n-1$个寿司,,,我开始调了半天没调出来$kk$
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define il inline
#define gc getchar()
#define mp make_pair
#define int long long
#define P pair<int,int>
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i) const int N=(<<)+,M=+;
int n,mod,sqt,f[N][N],g[][N][N],p[]={,,,,,,,},as,tot;
P nod[M]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void ad(ri &x,ri y){x+=y;if(x>=mod)x-=mod;} signed main()
{
//freopen("2150.in","r",stdin);freopen("2150.out","w",stdout);
n=read();mod=read();sqt=sqrt(n+);
rp(i,,n)
{ri nw=i;rp(j,,)if(!(nw%p[j])){nod[i].sc|=(<<j);while(!(nw%p[j]))nw/=p[j];}nod[i].fi=nw;}
sort(nod+,nod+n+);tot=(<<)-;f[][]=g[][][]=g[][][]=;
rp(i,,n)
{
my(j,tot,)
my(k,tot,)
{
if(j&k)continue;
if(!(j&nod[i].sc))ad(g[][j][k|nod[i].sc],g[][j][k]);
if(!(k&nod[i].sc))ad(g[][j|nod[i].sc][k],g[][j][k]);
}
if(nod[i].fi== || nod[i].fi^nod[i+].fi)
{
rp(j,,tot)rp(k,,tot)if(!(j&k))f[j][k]=(g[][j][k]+g[][j][k]-f[j][k])%mod,ad(f[j][k],mod);
memcpy(g[],f,sizeof(g[]));memcpy(g[],f,sizeof(g[]));
}
}
rp(i,,tot)rp(j,,tot)if(!(i&j))ad(as,f[i][j]);printf("%lld\n",as);
return ;
}
最新文章
- xmpp整理笔记:环境的快速配置(附安装包)
- Google Code Jam 2015 R1C B
- 查看linux [Fedora] 系统信息
- word插件开发 运行时,插件不启动.
- (sql server)数据分页的实现
- R语言和大数据
- 破解tumblr背景音乐
- 记一次 Newtonsoft.Json 巧妙的用法(C#)
- Oracle 子程序参数模式,IN,OUT,IN OUT
- HTTP发送RAW请求注意的问题
- 4-3 组件参数校验与非props特性
- Spring Data JPA Batch Insertion
- MySQL中死锁(转)
- Ubuntu自带截图工具screenshoot
- if 结构和三目运算和switch语句
- java中拼写xml
- Google官方网页载入速度检测工具PageSpeed Insights 使用教程
- 170522、Linux 平台通过 nginx 和 vsftpd 构建图片服务器
- springcloud19---springCloudConfig
- RabbitMQ延迟队列