欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.09.08 NOIP模拟 division(状压dp)

程序员文章站 2022-03-16 11:13:21
...

2018.09.08 NOIP模拟 division(状压dp)
2018.09.08 NOIP模拟 division(状压dp)
2018.09.08 NOIP模拟 division(状压dp)


这么sb的题考场居然写挂了2233。
假设n=iaiki
那么集合中合法的数一定满足:
t=i(1/aiki)
发现后面的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;
}
相关标签: dp