fork(5) download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<cstring>
  7. #include<map>
  8. #include<set>
  9. #include<stack>
  10. #include<queue>
  11. #include<string>
  12. #include<iterator>
  13. #include<string>
  14. #include<sstream>
  15. #include<cassert>
  16. #include<ctime>
  17. #include<cmath>
  18.  
  19. #define MP make_pair
  20. #define PB push_back
  21. #define X first
  22. #define Y second
  23. #define oo 2000000000
  24. #define MOD 1000000007
  25. #define LL long long int
  26. #define PII pair<int,int>
  27. #define DEBUG 0
  28.  
  29. using namespace std;
  30. int N,a,M,b;
  31. vector<int> adj[1002];
  32. bool mark[1002];
  33. bool vis[1002];
  34. vector<int> v,g;
  35. int cc,mp[1002],s1,s2;
  36.  
  37. void dfs(int u){
  38.     vis[u]=true;
  39.     v.PB(u);mp[u]=v.size()-1;
  40.     for(int i=0;i<adj[u].size();i++){
  41.         int v=adj[u][i];
  42.         if(vis[v]) continue;
  43.         dfs(v);
  44.     }
  45. }
  46. bool check(int mask,int l){
  47.     for(int i=0;i<l;i++) if(mask&1<<i){
  48.         int u=v[i],t;
  49.         for(int j=0;j<adj[u].size();j++){
  50.             t=mp[adj[u][j]];
  51.             if(t<l && (mask&1<<t)) return false;
  52.         }
  53.     }
  54.     return true;
  55. }
  56. bool check2(int mask,int l){
  57.     for(int i=0;i<l;i++) if(mask&1<<i){
  58.         int u=v[i+s1],t;
  59.         for(int j=0;j<adj[u].size();j++){
  60.             t=mp[adj[u][j]]-s1;
  61.             if(t>=0 && (mask&1<<t)) return false;
  62.         }
  63.     }
  64.     return true;
  65. }
  66. int main(){
  67.     int x;
  68.     memset(mark,false,sizeof(mark));
  69.     scanf("%d%d%d",&N,&a,&b);
  70.     scanf("%d",&M);
  71.     for(int i=0;i<M;i++) scanf("%d",&x), mark[x] = true;
  72.     for(int i=1;i<=N;i++){
  73.         if(mark[i]) continue;
  74.         if(i*a <= N && !mark[i*a]){
  75.             adj[i].PB(i*a);
  76.             adj[i*a].PB(i);
  77.         }
  78.         if(i*b <= N && !mark[i*b]){
  79.             adj[i].PB(i*b);
  80.             adj[i*b].PB(i);
  81.         }
  82.     }
  83.     LL ans=1;
  84.     memset(vis,false,sizeof(vis));
  85.     for(int i=1;i<=N;i++){
  86.         if(mark[i]) continue;
  87.         if(!vis[i]){
  88.             LL cnt=0;v.clear();g.clear();
  89.             dfs(i);
  90.             cc=v.size();s1=cc/2,s2=cc-s1;
  91.             assert(s1<=20 && s2<=20);
  92.             //for(int i=0;i<v.size();i++) printf("(%d,%d)\n",i,v[i]);
  93.             for(int i=0;i<(1<<s1);i++){
  94.                 if(!check(i,s1)) continue;
  95.                 else g.PB(i);//, printf("g : %d\n",i);
  96.             }
  97.             //printf("%d\n",g.size());
  98.             int mask;
  99.             for(int i=0;i<(1<<s2);i++){
  100.                 if(!check2(i,s2)) continue;
  101.                 else{
  102.                     if(!i){
  103.                         cnt+=g.size();
  104.                         continue;
  105.                     }
  106.                     mask=(1<<s1)-1;
  107.                     for(int j=0;j<s2;j++){
  108.                         if(!(i&(1<<j)) ) continue;
  109.                         int u=v[s1+j];
  110.                         for(int k=0;k<adj[u].size();k++){
  111.                             if(mp[adj[u][k]] >= s1) assert(!( i & 1 << (mp[adj[u][k]]-s1)) );
  112.                             if(mp[adj[u][k]] < s1) mask&=~(1<<mp[adj[u][k]]);
  113.                         }
  114.                     }
  115.                     //printf("i = %d , mask = %d\n",i,mask);
  116.                     mask=~mask;
  117.                     for(int j=0;j<g.size();j++) cnt+=(!(mask&g[j]));
  118.                     //printf("cnt = %lld\n",cnt);
  119.                 }
  120.             }
  121.             cnt%=MOD;
  122.             //printf("%lld\n",cnt);
  123.             ans=(ans*cnt)%MOD;
  124.         }
  125.     }
  126.     printf("%lld\n",ans);
  127.     return 0;
  128. }
  129.  
Success #stdin #stdout 0s 2920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/jdUeEa
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!