首页 > 代码库 > hdu4623：crime 数学优化dp
hdu4623：crime 数学优化dp
鞍山热身赛的题，也是去年多校原题
题目大意：
求n个数的排列中满足相邻两个数互质的排列的数量并取模
当时的思路就是状压dp.. dp[i][state] state用二进制记录某个数是否被取走，i 表示当前序列末尾的数字
然后gcd状态转移
可是n是28，算了一下有几亿个状态。。没法做。。
回来之后找了题解发现可以用数学方法优化，于是搞了半天终于ac了
首先在这个问题中：
两个数是否互质只与他们的质因数有关，所以质因数相同的数是等价的，称作此问题的等价类
质因数找到这些等价类，并得到每个类中的数的数量是很容易的。。
所以只需要对这些等价类进行处理，最后对每个等价类再乘以数量的排列数就可以得到答案了。
不过此时有了数量，就不能用二进制状压了，应该采用哈希来状压。
研究了一会发现哈希状压和二进制状压差不多，只不过把基数从(1+1)^n变成了 (num[1]+1)*(num[2]+1)....也是很好理解的
这些状态处理完，发现对于n=28只有 5600000个状态了，等价类数是17 所以复杂度是17*5600000
一交MLE了。由于取模最大30000，把数组改为short，中间结果int防溢出，不爆内存了。
然后时限30s，以为可以过，结果又T了。。
于是又想了一会，发现17，19，23这三个数与其他任意一个数的互质。。所以他们与 1 是等价的
加了这个优化以后复杂度下降到约为 14*1800000
8800ms AC...
代码如下
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int prime[]={2,3,5,7,11,13,17,19,23};const int np=9;int state[30];int g[300][300];int vi[300];int num[30];int base[30];short dp[19][2000000];bool ok[29];int n,m,ns,st;void ini(){ scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); memset(vi,0,sizeof(vi)); memset(num,0,sizeof(num)); ns=0; state[++ns]=0; num[ns]=1; for(int i=2;i<=n;i++) { st=0; if(ok[i]) { num[1]++; continue; } for(int j=0;j<np;j++) { if(i%prime[j]==0) { st|=(1<<j); } } if(!vi[st]) { state[++ns]=st; num[ns]=1; vi[st]=ns; } else { num[vi[st]]++; } } for(int i=1;i<=ns;i++) { for(int j=1;j<=ns;j++) { if((state[i]&state[j])==0) g[i][j]=1; } } base[1]=1; st=0; for(int i=1;i<=ns;i++) { base[i+1]=base[i]*(num[i]+1); st+=base[i]*num[i]; }}int getnum(int i,int x){ int res=(x%base[i+1])/(base[i]); return res;}int getstate(int i,int num){ return num*base[i];}void dfs(int t,int x){ if(t==0) { dp[x][0]=1; return ; } if(dp[x][t]!=-1) return; dp[x][t]=0; for(int i=1;i<=ns;i++) { if(g[x][i]&&getnum(i,t)>=1) { dfs(t-base[i],i); dp[x][t]=((int)dp[x][t]+dp[i][t-base[i]])%m; } } return;}int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif // ONLINE_JUDGE int T; scanf("%d",&T); memset(ok,0,sizeof(ok)); ok[17]=1; ok[19]=1; ok[23]=1; while(T--) { ini(); memset(dp,-1,sizeof(dp)); int ans=0; for(int i=1;i<=ns;i++) { dfs(st-base[i],i); ans=((int)ans+dp[i][st-base[i]])%m; } for(int i=1;i<=ns;i++) { while(num[i]>1) { ans=((int)ans*num[i])%m; num[i]--; } } printf("%d\n",ans); }}
hdu4623：crime 数学优化dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。