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

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

题目大意：

小a终于放假了，它想在假期中去一些地方游玩，现在有N个景点，编号为

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

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

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

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

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

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

打表代码：

  1 #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模板：

  1 #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
",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
",linear_seq::gao(VI{0,0,3,30,195,1050,5103,23310,102315,437250},n-1));
127 }

View Code