小a的旅行计划（BM模板）

题目链接：https://ac.nowcoder.com/acm/contest/223/B

题目大意：

小a终于放假了，它想在假期中去一些地方游玩，现在有N个景点，编号为$\mathrm{1,2,\dots N1,2,\dots N，同时小b也想出去游玩。由于一些特殊♂原因，他们的旅行计划必须满足一些条件}$

首先，他们可以从这N个景点中任意选几个游玩

设小a选出的景点集合为A，小b选的景点集合为B，则需要满足

1. A,B的交集不能为空集

2. A,B不能相互包含(A=B也属于相互包含)

注意：在这里我们认为(A,B)是无序的，即(A,B)和(B,A)是同一种方案。

具体思路：暴力打表，然后把前15项放进BM里，然后就A了？

打表代码：

#include<bits/stdc++.h>  2 using namespace std;  3 # define ll long long  4 const int maxn = 2e5 + 100;  5 const int N = 100;  6 ll n;  7 map<vector<ll>,bool>vis;  8 map<pair<vector<ll>,vector<ll>>,bool >vis2;  9 map<int,int>bao;  10 bool judge(vector<ll>q1,vector<ll>q2)  11 {  12 int flag=1;  13 if(q1==q2)  14 return false;  15  bao.clear();  16 for(int i=0; i<q1.size(); i++)  17  {  18 bao[q1[i]]=1;  19  }  20 for(int i=0; i<q1.size(); i++)  21  {  22 for(int j=0; j<q2.size(); j++)  23  {  24 if(q1[i]==q2[j])  25  {  26 flag=0;  27 break;  28  }  29  }  30 if(!flag)  31 break;  32  }  33 if(flag)  34 return false;  35 int num=0;  36 for(int i=0; i<q2.size(); i++)  37  {  38 if(bao[q2[i]])  39 num++;  40  }  41 if(num==q2.size())  42 return false;  43  bao.clear();  44 for(int i=0; i<q2.size(); i++)  45  {  46 bao[q2[i]]=1;  47  }  48 num=0;  49 for(int i=0; i<q1.size(); i++)  50  {  51 if(bao[q1[i]])  52 num++;  53  }  54 if(num==q1.size())  55 return false;  56 return true;  57 }  58 vector<ll>q1;  59 vector<ll>q2;  60 bool check(ll tmp1,ll tmp2)  61 {  62  q1.clear();  63  q2.clear();  64 for(ll i=0; i<n; i++)  65  {  66 if((1ll<<i)&tmp1)  67  q1.push_back(i);  68  }  69 for(ll i=0; i<n; i++)  70  {  71 if((1ll<<i)&tmp2)  72  q2.push_back(i);  73  }  74  sort(q1.begin(),q1.end());  75  sort(q2.begin(),q2.end());  76 if(judge(q1,q2))  77 return true;  78 return false;  79 }  80 ll cal(ll n)  81 {  82 ll maxstate=(1ll<<n)-1;  83 ll sum=0;  84 for(ll i=0; i<=maxstate; i++)  85  {  86 for(ll j=0; j<=maxstate; j++)  87  {  88 if(check(i,j)&&vis2[make_pair(q1,q2)]==0)  89  {  90 vis2[make_pair(q1,q2)]=1;  91 vis2[make_pair(q2,q1)]=1;  92 sum++;  93  }  94  }  95  }  96 return sum;  97 }  98 int main()  99 { 100 // freopen("hqx.out","w",stdout); 101 //scanf("%d",&n); 102 for(ll i=1; i<=10; i++) 103  { 104 n=i; 105  vis.clear(); 106  vis2.clear(); 107 printf("%lld ",cal(n)); 108  } 109 110 return 0; 111 }

BM模板：

#include <bits/stdc++.h>  2  3 using namespace std;  4 #define rep(i,a,n) for (long long i=a;i<n;i++)  5 #define per(i,a,n) for (long long i=n-1;i>=a;i--)  6 #define pb push_back  7 #define mp make_pair  8 #define all(x) (x).begin(),(x).end()  9 #define fi first  10 #define se second  11 #define SZ(x) ((long long)(x).size())  12 typedef vector<long long> VI;  13 typedef long long ll;  14 typedef pair<long long,long long> PII;  15 const ll mod=1e8+7;  16 ll powmod(ll a,ll b)  17 {  18 ll res=1;  19 a%=mod;  20 assert(b>=0);  21 for(; b; b>>=1)  22  {  23 if(b&1)  24 res=res*a%mod;  25 a=a*a%mod;  26  }  27 return res;  28 }  29 // head  30  31 long long _,n;  32 namespace linear_seq  33 {  34 const long long N=10010;  35 ll res[N],base[N],_c[N],_md[N];  36  37 vector<long long> Md;  38 void mul(ll *a,ll *b,long long k)  39 {  40 rep(i,0,k+k) _c[i]=0;  41 rep(i,0,k) if (a[i])  42 rep(j,0,k)  43 _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;  44 for (long long i=k+k-1; i>=k; i--)  45 if (_c[i])  46 rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;  47 rep(i,0,k) a[i]=_c[i];  48 }  49 long long solve(ll n,VI a,VI b)  50 {  51 // a 系数 b 初值 b[n+1]=a[0]*b[n]+...  52 // printf("%d\n",SZ(b));  53 ll ans=0,pnt=0;  54 long long k=SZ(a);  55 assert(SZ(a)==SZ(b));  56 rep(i,0,k) _md[k-1-i]=-a[i];  57 _md[k]=1;  58  Md.clear();  59 rep(i,0,k) if (_md[i]!=0)  60  Md.push_back(i);  61 rep(i,0,k) res[i]=base[i]=0;  62 res[0]=1;  63 while ((1ll<<pnt)<=n)  64 pnt++;  65 for (long long p=pnt; p>=0; p--)  66  {  67  mul(res,res,k);  68 if ((n>>p)&1)  69  {  70 for (long long i=k-1; i>=0; i--)  71 res[i+1]=res[i];  72 res[0]=0;  73 rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;  74  }  75  }  76 rep(i,0,k) ans=(ans+res[i]*b[i])%mod;  77 if (ans<0)  78 ans+=mod;  79 return ans;  80 }  81 VI BM(VI s)  82 {  83 VI C(1,1),B(1,1);  84 long long L=0,m=1,b=1;  85 rep(n,0,SZ(s))  86  {  87 ll d=0;  88 rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;  89 if (d==0)  90 ++m;  91 else if (2*L<=n)  92  {  93 VI T=C;  94 ll c=mod-d*powmod(b,mod-2)%mod;  95 while (SZ(C)<SZ(B)+m)  96 C.pb(0);  97 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;  98 L=n+1-L;  99 B=T; 100 b=d; 101 m=1; 102  } 103 else 104  { 105 ll c=mod-d*powmod(b,mod-2)%mod; 106 while (SZ(C)<SZ(B)+m) 107 C.pb(0); 108 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; 109 ++m; 110  } 111  } 112 return C; 113 } 114 long long gao(VI a,ll n) 115 { 116 VI c=BM(a); 117  c.erase(c.begin()); 118 rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod; 119 return solve(n,c,VI(a.begin(),a.begin()+SZ(c))); 120 } 121 }; 122 123 int main() 124 { 125 scanf("%lld", &n); 126 printf("%lld\n",linear_seq::gao(VI{0,0,3,30,195,1050,5103,23310,102315,437250},n-1)); 127 }