2018.09.08 NOIP模拟 division(状压dp)
程序员文章站
2022-03-16 11:13:21
...
这么sb的题考场居然写挂了2233。
假设
那么集合中合法的数一定满足:
发现后面的i很小,可以状压dp一发。
然后就没了。
注意集合中有1时需要把答案乘二。
代码:
#include<bits/stdc++.h>
#define N 100005
#define first xx
#define second yy
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int a[505],m,tot=0,divv[N],cal[N],siz=0,dp[1<<20],sta[N];
ll n;
map<int,bool>in;
inline bool check(int x){
if(n%x)return false;
int t=sqrt(x),tmp=x;
bool f=true;
for(int i=2;i<=t;++i){
if(tmp==1)break;
if(tmp%i)continue;
while(tmp%i==0)tmp/=i;
if(!in[i])in[i]=true,divv[++siz]=i;
if(n/x%i==0)f=false;
}
if(tmp!=1&&!in[tmp])in[tmp]=true,divv[++siz]=tmp;
if(!f)return false;
if(tmp==1)return true;
if(n/x%tmp==0)return false;
return true;
}
int main(){
n=read(),m=read(),dp[0]=1;
for(int i=1;i<=m;++i){
int x=read();
if(x==1){dp[0]=2;continue;}
if(check(x))a[++tot]=x;
}
if(!tot){cout<<"0";return 0;}
sort(divv+1,divv+siz+1);
for(int i=1;i<=siz;++i){
ll tmp=n;
while(tmp%divv[i]==0)tmp/=divv[i];
}
for(int i=1;i<=tot;++i)for(int j=1;j<=siz;++j)if(a[i]%divv[j]==0)sta[i]|=1<<(j-1);
for(int i=0;i<(1<<siz);++i)for(int j=1;j<=tot;++j)
if((i&sta[j])==0&&i<sta[j])dp[i|sta[j]]+=dp[i];
cout<<dp[(1<<siz)-1];
return 0;
}