第一题
具体思路:状压DP
f[i][j]表示最后一个点是i,选了j这些点的方案数
AC代码
#pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<bits/stdc++.h> using namespace std; int n,i,j,x[100],y[100],must[100][100],k; int dp[21][1010000],ha=100000007;; double dis(int a,int b) { return sqrt((double)(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])); } bool on(int a,int b,int c) { if(fabs(dis(a,b)+dis(a,c)-dis(b,c))<1e-6)return 1;else return 0; } int main() { scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) { int now=0; for(k=1;k<=n;k++) if(on(k,i,j)) { now|=(1<<(k-1)); } must[i][j]=now; } for(i=1;i<=n;i++)dp[i][1<<(i-1)]=1; for(j=0;j<=(1<<n)-1;j++) for(i=1;i<=n;i++) if(j&(1<<(i-1))) { for(k=1;k<=n;k++) if((j&(1<<(k-1)))==0) { int now=j|(1<<(k-1)); if(must[i][k]==(must[i][k]&now)) { dp[k][now]=(dp[k][now]+dp[i][j])%ha; } } } int ans=0; for(i=1;i<=n;i++) for(j=0;j<=(1<<n)-1;j++) if((1<<(i-1)&j)) { int tot=0; for(k=1;k<=n;k++) if((1<<(k-1)&j))tot++; if(tot>=4)ans=(ans+dp[i][j])%ha; } printf("%d",ans); return 0; }
第二题
具体思路:ans=(2^(n+1))/3
加个高精度就好了
AC代码
#include<bits/stdc++.h> #define LL long long const LL MAX_LEN=50004; const LL base=1e8; const int baselen=8; using namespace std; int n,i,j; namespace BigNumber{ const int L=10010,Base=10000,Bit=4; const LL MaxInt=2147483647; const int Pw10[15]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; const int Pw2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536}; LL DOF[L]; struct BigNum{ int v[L],le,flag; BigNum(){ memset(v,0,sizeof v); le=flag=1; } BigNum(int x){ flag=1; le=1; memset(v,0,sizeof v); if (x<0) flag=-1,x=-x; v[1]=x; while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le; } BigNum(LL x){ flag=1; le=1; memset(v,0,sizeof v); if (x<0) flag=-1,x=-x; v[1]=x%Base; v[2]=x/Base%Base; v[3]=x/Base/Base%Base; v[4]=x/Base/Base/Base; le=4; while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le; while (v[le]==0 && le>1) --le; } BigNum(int len,int fir){ memset(v,0,sizeof v); le=len; v[le]=fir; flag=1; } BigNum(const BigNum &a,int x){ memset(v,0,sizeof v); le=a.le+x; flag=a.flag; for (int i=1;i<=a.le;++i) v[i+x]=a.v[i]; } int IntoInt(){ if (le>3) cerr <<"error: cannot change so big into int!"<<endl; LL d=0; for (int i=le;i>=1;--i) d=d*Base+v[i]; if (flag==-1) d=-d; if (d>MaxInt || -d<MaxInt+1) cerr <<"error: cannot change so big into int!"<<endl; return d; } void Clear(){ memset(v,0,sizeof v); le=flag=1; } void operator =(int a){ if (a < 0) flag=-1,a=-a; le=1; v[1]=a; while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le; } //Compare --> bool operator ==(const BigNum &a)const{ if (le!=a.le || flag!=a.flag) return 0; for (int i=1;i<=le;++i) if (v[i]!=a.v[i]) return 0; return 1; } bool operator <(const BigNum &a)const{ if (flag<a.flag || flag==a.flag && le<a.le) return 1; if (flag>a.flag || flag==a.flag && le>a.le) return 0; for (int i=le;i>=1;--i){ if (v[i]<a.v[i]) return flag==1? 1:0; if (v[i]>a.v[i]) return flag==1? 0:1; }return 0; } bool operator >(const BigNum &a)const{ if (flag<a.flag || flag==a.flag && le<a.le) return 0; if (flag>a.flag || flag==a.flag && le>a.le) return 1; for (int i=le;i>=1;--i){ if (v[i]<a.v[i]) return flag==1? 0:1; if (v[i]>a.v[i]) return flag==1? 1:0; }return 0; } bool operator ==(const int &x)const{ return *this == BigNum(x); } //Add and Sub --> void operator +=(const BigNum &x){ BigNum a=*this; BigNum b=x; memset(v,0,sizeof v); flag=1; if (a.flag==-1 && b.flag==-1){ flag=-1; a.flag=1; b.flag=1; } if (a < b) swap(a,b); if (b.flag==-1){ b.flag=1; if (a < b) swap(a,b),flag=-1; b.flag=-1; } if (b.flag==1){ le=a.le; for (int i=1;i<=le;++i) v[i]=a.v[i]+b.v[i]; for (int i=1;i<=le;++i) v[i+1]+=v[i]/Base,v[i]%=Base; while (v[le+1]>0) ++le; }else{ le=a.le; for (int i=1;i<=le;++i) v[i]=a.v[i]-b.v[i]; for (int i=1;i<=le;++i) if (v[i]<0) --v[i+1],v[i]+=Base; while (v[le]==0 && le>1) --le; } } void operator +=(int x){ *this += BigNum(x); } void operator -=(const BigNum &x){ BigNum a=x; a.flag=-a.flag; *this += a; } void operator -=(int x){ *this -= BigNum(x); } BigNum &operator ++(){ return *this += 1, *this; } BigNum &operator --(){ return *this -= 1, *this; } BigNum operator ++(int){ BigNum c(*this); ++ *this; return c; } BigNum operator --(int){ BigNum c(*this); -- *this; return c; } //Mul --> void operator *=(const BigNum &x){ BigNum a=x; if (flag==a.flag) flag=1;else flag=-1; a.flag=1; memset(DOF,0,sizeof DOF); for (int i=1;i<=le;++i) for (int j=1;j<=a.le;++j) DOF[i+j-1]+=v[i]*a.v[j]; le+=a.le+9; for (int i=1;i<=le;++i) DOF[i+1]+=DOF[i]/Base,DOF[i]%=Base; while (DOF[le]==0 && le>1) --le; for (int i=1;i<=le;++i) v[i]=DOF[i]; } void operator *=(const int &x){ *this *= BigNum(x); } void operator *=(const LL &x){ *this *= BigNum(x); } //Div --> void operator /=(const int &x){ BigNum a; a=x; if (flag==a.flag) flag=1;else flag=-1; a.flag=1; memset(DOF,0,sizeof DOF); LL rest=0; for (int i=le;i>=1;--i){ rest=rest*Base+v[i]; DOF[i]=rest/x; rest%=x; v[i]=0; } for (int i=le;i>=1;--i) v[i]=DOF[i]; while (v[le]==0 && le>1) --le; } /*void operator /=(const BigNum &x){ BigNum a=*this,b=x,c; if (a.flag==b.flag) flag=1;else flag=-1; a.flag=b.flag=1; if (le-b.le<=3){ LL l=0,r=1e12,ans=-1; while (l<=r){ LL mid=(l+r)>>1; c=b; c*=mid; if (!(c > a)) ans=mid,l=mid+1; else r=mid-1; } *this = BigNum(ans); return; }else{ for (int i=le;i>=1;--i){ int l=0,r=Base,ans=-1; while (l<=r){ int mid=(l+r)>>1; c=BigNum(i,mid); c*=b; if (!(c > a)) ans=mid,l=mid+1; else r=mid-1; } v[i]=ans; c=BigNum(i,ans); c*=b; a-=c; } while (v[le]==0 && le>1) --le; } }*/ void operator /=(const BigNum &x){ BigNum a=*this,b=x,c,d; if (a.flag==b.flag) flag=1;else flag=-1; for (int i=le;i>0;--i) v[i]=0; le=a.le-b.le+1; for (int i=le;i>=1;--i){ //cerr <<i<<endl; c=BigNum(b,i-1); for (int j=log2(Base);j>=0;--j){ d=c; d*=Pw2[j]; if (!(a < d)) v[i]+=Pw2[j],a-=d; } } for (int i=1;i<=le;++i) v[i+1]+=v[i]/Base,v[i]%=Base; while (v[le+1]>0) ++le; while (v[le]==0 && le>1) --le; } //Mod --> void operator %=(int p){ LL d=0; if (p < 0) p=-p; for (int i=le;i>=1;--i) d=(d*Base+v[i])%p,v[i]=0; le=1; v[1]=d; while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le; } void operator %=(const BigNum &x){ BigNum a=*this,b=x,c,d; for (int i=le;i>0;--i) v[i]=0; le=a.le-b.le+1; for (int i=le;i>=1;--i){ //cerr <<i<<endl; c=BigNum(b,i-1); for (int j=log2(Base);j>=0;--j){ d=c; d*=Pw2[j]; if (!(a < d)) a-=d; } } *this = a; } //Power --> BigNum pow(int b){ BigNum a,c; a=*this; c=1; for (;b;b>>=1,a*=a) if (b&1) c*=a; return c; } BigNum pow(int x,int b){ BigNum c,a; c=1; a=x; for (;b;b>>=1,a*=a) if (b&1) c*=x; return c; } int pow2(int a,int b){ int c=1; for (;b;b>>=1,a*=a) if (b&1) c*=a; return c; } //Shr and Shl --> void operator <<=(int x){ if (x<=30) *this *= pow2(2,x); else *this *= pow(2,x); } void operator >>=(int x){ if (x<=30) *this /= pow2(2,x); else *this /= pow(2,x); } }; //Compare --> bool operator ==(const int &a,const BigNum &b){ return b == a; } bool operator !=(const BigNum &a,const BigNum &b){ return !(a == b); } bool operator !=(const BigNum &a,const int &b){ return !(a == b); } bool operator !=(const int &a,const BigNum &b){ return !(b == a); } bool operator <(const BigNum &a,const int &b){ return a < BigNum(b); } bool operator <(const int &a,const BigNum &b){ return BigNum(a) < b; } bool operator >(const BigNum &a,const int &b){ return a > BigNum(b); } bool operator >(const int &a,const BigNum &b){ return BigNum(a) > b; } bool operator <=(const BigNum &a,const BigNum &b){ if (a > b) return 0; return 1; } bool operator >=(const BigNum &a,const BigNum &b){ if (a < b) return 0; return 1; } bool operator <=(const BigNum &a,const int &b){ if (a > b) return 0; return 1; } bool operator <=(const int &a,const BigNum &b){ if (a > b) return 0; return 1; } bool operator >=(const BigNum &a,const int &b){ if (a < b) return 0; return 1; } bool operator >=(const int &a,const BigNum &b){ if (a < b) return 0; return 1; } int max(const int &a,const int &b){ if (a < b) return b; return a; } int min(const int &a,const int &b){ if (a < b) return a; return b; } BigNum max(const BigNum &a,const BigNum &b){ if (a < b) return b; return a; } BigNum min(const BigNum &a,const BigNum &b){ if (a < b) return a; return b; } //Add --> BigNum operator +(const BigNum &a,const BigNum &b){ BigNum c=a; c+=b; return c; } BigNum operator +(const BigNum &a,const int &b){ BigNum c=a; c+=b; return c; } BigNum operator +(const int &a,const BigNum &b){ BigNum c=b; c+=a; return c; } //Sub --> BigNum operator -(const BigNum &a,const BigNum &b){ BigNum c=a; c-=b; return c; } BigNum operator -(const BigNum &a,const int &b){ BigNum c=a; c-=b; return c; } BigNum operator -(const int &a,const BigNum &b){ BigNum c=b; c-=a; return c; } //Mul --> BigNum operator *(const BigNum &a,const BigNum &b){ BigNum c=a; c*=b; return c; } BigNum operator *(const BigNum &a,const int &b){ BigNum c=a; c*=b; return c; } BigNum operator *(const int &a,const BigNum &b){ BigNum c=b; c*=a; return c; } //Div --> BigNum operator /(const BigNum &a,const int &b){ BigNum c=a; c/=b; return c; } BigNum operator /(const int &a,const BigNum &b){ BigNum c=b; c/=a; return c; } BigNum operator /(const BigNum &a,const BigNum &b){ BigNum c=a; c/=b; return c; } //Mod --> BigNum operator %(const BigNum &a,const int &b){ BigNum c=a; c%=b; return c; } BigNum operator %(const int &a,const BigNum &b){ BigNum c=b; c%=a; return c; } BigNum operator %(const BigNum &a,const BigNum &b){ BigNum c=a; c%=b; return c; } //Shr and Shl --> BigNum operator <<(const BigNum &a,const int b){ BigNum c=a; c<<=b; return c; } BigNum operator <<(const BigNum &a,BigNum &b){ return a << b.IntoInt(); } BigNum operator >>(const BigNum &a,const int &b){ BigNum c=a; c>>=b; return c; } BigNum operator >>(const BigNum &a,BigNum &b){ return a >> b.IntoInt(); } //Read and Print --> string yz; char cyz; void Read(BigNum &a){ a.Clear(); while (cin.peek()==' ') getchar(); if (cin.peek()=='-'){ a.flag=-1; cin >>cyz; } cin >>yz; int len=yz.length(); a.le=len/Bit; for (int i=1;i<=a.le;++i){ int l=len-Bit*i,r=l+Bit-1; for (int j=l;j<=r;++j) a.v[i]=a.v[i]*10+yz[j]-'0'; } if(len%Bit!=0){ int r=len-Bit*a.le-1; ++a.le; for (int j=0;j<=r;++j) a.v[a.le]=a.v[a.le]*10+yz[j]-'0'; } } void PrintWith(int x,int k){ for (int i=k-1;i>=0;--i) if (Pw10[i]>x) putchar('0'); else putchar(x/Pw10[i]+'0'),x%=Pw10[i]; } void Print(const BigNum &a){ if (a.flag==-1) putchar('-'); printf("%d",a.v[a.le]); for (int i=a.le-1;i>=1;--i) PrintWith(a.v[i],Bit); } void Println(const BigNum &a){ Print(a); puts(""); } }; using namespace BigNumber; BigNum a,ans; int x,b; int main() { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&x); a=2;b=(x+1);ans=1; while(b>0) { if(b%2)ans=ans*a; b=b/2; a=a*a; } ans=ans/3; Println(ans); } return 0; }
第三题
具体思路:莫队
记录一下前缀异或和就好了
AC代码
#include<bits/stdc++.h> using namespace std; #define int long long int n,m,i,j,a[500000],k,ans,L,R,now[500000],sum[500000],answer[500000],tot,num[500000]; struct ask { int l,r,id; }q[500000]; bool cmp(ask a,ask b) { if(num[a.l]!=num[b.l])return (num[a.l])<(num[b.l]);else return a.r<b.r; } void del(int x) { tot-=now[k^sum[x]]; now[sum[x]]--; if(sum[x]==k)tot--; } void add(int x) { tot+=now[k^sum[x]]; now[sum[x]]++; if(sum[x]==k)tot++; } main() { scanf("%lld%lld%lld",&n,&m,&k); for(i=1;i<=n;i++)scanf("%lld",&a[i]),sum[i]=sum[i-1]^a[i],num[i]=i/sqrt(n); for(i=1;i<=m;i++)scanf("%lld%lld",&q[i].l,&q[i].r),q[i].id=i; sort(q+1,q+1+m,cmp); L=1,R=0; for(i=1;i<=m;i++) { while(L<q[i].l)del(L-1),L++; while(L>q[i].l)L--,add(L-1); while(R<q[i].r)R++,add(R); while(R>q[i].r)del(R),R--; answer[q[i].id]=tot; } for(i=1;i<=m;i++)printf("%lld ",answer[i]); return 0; }