牛客多校第九场
A: Circulant Matrix
已知序列a和x的fwt结果是b，知道a和b求x。
其实就是FWT的逆过程。先对b做ufwt，对a做fwt，然后x就是b/a。之后对得到的x做一遍fwt即可。
#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <string> #include <map> using namespace std; typedef long long LL ; const long long mod=1e9+7; long long rev; long long qp(long long p,long long q) { long long cnt=1; while(q>0) { if(q&1) cnt=cnt*p%mod; p=p*p%mod; q>>=1; } return cnt; } class FWT{ public: void fwt(LL *a, int n){ for(int d = 1; d < n; d <<= 1){ for(int m = d<<1, i = 0; i < n; i += m){ for(int j = 0; j < d; j++){ LL x = a[i+j], y = a[i+j+d]; a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod; //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod; //and:a[i+j]=x+y; //or:a[i+j+d]=x+y; } } } } void ufwt(LL *a, int n){ for(int d = 1; d < n; d <<= 1){ for(int m = d<<1, i = 0; i < n; i += m){ for(int j = 0; j < d; j++){ LL x = a[i+j], y = a[i+j+d]; a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod; //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2; //and:a[i+j]=x-y; //or:a[i+j+d]=y-x; } } } } void work(LL *a, LL *b, int n){ fwt(a, n); fwt(b, n); for(int i = 0; i < n; i++) a[i] *= b[i]; ufwt(a, n); } }myfwt; long long ai[600010],bi[600010],xi[600010]; int n; int main() { rev=qp(2,mod-2); int i,j; scanf("%d",&n); int m=1; while(m<=n) m<<=1; for(i=0;i<n;i++) scanf("%lld",&ai[i]); for(i=0;i<n;i++) scanf("%lld",&bi[i]); myfwt.ufwt(bi,m); myfwt.fwt(ai,m); for(i=0;i<m;i++) { xi[i]=bi[i]*qp(ai[i],mod-2)%mod; } myfwt.fwt(xi,m); for(i=0;i<n;i++) { printf("%lld\n",xi[i]); } return 0; }
View Code
B：Enumeration not optimization
C: Gambling
D: The number of circuits
求欧拉回路的结论题。首先用BEST theorem定理暴力算小数据，大胆猜测是线性递推（可以观察证明）。在用强大的Berlekamp Massey 算法解出线性递推（这个算法好像只能处理模为质数）。
#include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} // head namespace linear_seq { const int N=10010; ll res[N],base[N],_c[N],_md[N]; vector<int> Md; void mul(ll *a,ll *b,int k) { rep(i,0,k+k) _c[i]=0; rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod; for (int i=k+k-1;i>=k;i--) if (_c[i]) rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod; rep(i,0,k) a[i]=_c[i]; } int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+... // printf("SIZE %d\n",SZ(b)); ll ans=0,pnt=0; int k=SZ(a); assert(SZ(a)==SZ(b)); rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1; Md.clear(); rep(i,0,k) if (_md[i]!=0) Md.push_back(i); rep(i,0,k) res[i]=base[i]=0; res[0]=1; while ((1ll<<pnt)<=n) pnt++; for (int p=pnt;p>=0;p--) { mul(res,res,k); if ((n>>p)&1) { for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0; rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod; } } rep(i,0,k) ans=(ans+res[i]*b[i])%mod; if (ans<0) ans+=mod; return ans; } VI BM(VI s) { VI C(1,1),B(1,1); int L=0,m=1,b=1; rep(n,0,SZ(s)) { ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod; if (d==0) ++m; else if (2*L<=n) { VI T=C; ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)<SZ(B)+m) C.pb(0); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; L=n+1-L; B=T; b=d; m=1; } else { ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)<SZ(B)+m) C.pb(0); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; ++m; } } return C; } int gao(VI a,ll n) { VI c=BM(a); c.erase(c.begin()); rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod; return solve(n,c,VI(a.begin(),a.begin()+SZ(c))); } }; long long det(int n,int a[][2010]) { //填矩阵大小 long long ans = 1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { while (a[j][i] != 0) { int u = a[i][i] / a[j][i]; for (int k = 0; k < n; k++) { int t = (a[i][k] - (long long)a[j][k] * u % mod + mod) % mod; a[i][k] = a[j][k]; a[j][k] = t; } ans = -ans; } } ans = ans * a[i][i] % mod; } if (ans < 0) { ans += mod; } return ans; } int a[2010][2010]; int qp(int p,int q) { int cnt=1; while(q>0) { if(q&1) cnt=(long long)cnt*p%mod; p=(long long)p*p%mod; q>>=1; } return cnt; } int solve(int n,int k) { int i,j; memset(a,0,sizeof(a)); for(i=0;i<n;i++) { a[i][i]=k; for(j=1;j<=k;j++) a[i][(i+j)%n]=-1; } int ans=det(n-1,a); int fac=1; for(i=2;i<k;i++) fac=fac*i%mod; ans=(long long)ans*qp(fac,n)%mod; return ans; } int main() { int n,k; int i; scanf("%d%d",&k,&n); vector<int> num; for(i=2*k+1;i <= (1 << k) + 2 * k + 1;i++) { num.push_back(solve(i,k)); } int ans=linear_seq::gao(num,n-(2*k+1)); printf("%d\n",ans); return 0; }
View Code
E: Music Game
期望算贡献，枚举连续的段，算一下这一个段对答案的贡献即可。注意的是枚举连续的段就必须把这一段的两端边界处不成功的概率算进去。
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <cmath> #include <vector> #include <iostream> #include <stack> #include <set> #include <map> #include <string> #define pi acos(-1.0) using namespace std; const int MAX=1e5+5; const int mod=1e9+7; int n,m; long long p[MAX],inv[MAX]; long long dp[MAX]; long long mi[MAX]; long long quickpow(long long x,long long n){ if(n==0) return 1; long long res=quickpow(x*x%mod,n/2); if(n%2) res=res*x%mod; return res; } int main(){ int i,j; long long inv_100=quickpow(100,mod-2); scanf("%d%d",&n,&m); mi[0]=1; for(i=1;i<=n;i++) { scanf("%lld",&p[i]); p[i]=(p[i]*inv_100)%mod; mi[i]=quickpow(i,m); } dp[0]=1; long long ans=0; for(i=1;i<=n;i++){ long long cnt=1; for(j=i;j<=n;j++) { cnt=cnt*p[j]%mod; long long tmp=mi[j-i+1]*cnt%mod; if(i>1) tmp=tmp*(1-p[i-1])%mod; if(i<n) tmp=(tmp*(1-p[j+1]))%mod; if(tmp<0) tmp+=mod; ans=(ans+tmp)%mod; } } printf("%lld\n",ans); return 0; }
View Code
F: Typing practice
G: Longest Common Subsequence
H: Prefix Sum
对操作暴力分块，还是第一次遇到这种分块。首先要看出单点修改对单点查询的贡献是可以O(1)计算的。那么我们把操作分成size块，对于块内的询问就暴力枚举块内修改操作对这个询问的影响，复杂度是O(q*size)，处理完一个块后重新构造一下这个前缀矩阵，复杂度是O(n*k*q/size)，所以总复杂度是O(n*k*q/size+q*size)，均值一下可以知道size=sqrt(n*k)时最优。
#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <string> #include <map> using namespace std; const long long mod=1e9+7; struct node { int x; long long y; node(){} node(int _x,long long _y):x(_x),y(_y){ } }; vector<node> qu; int n,q,k; long long c[45][100010],num[45][100010]; void init() { int i,j; for(i=1;i<=k;i++) { num[i][0]=num[i-1][0]; for(j=1;j<=n;j++) num[i][j]=(num[i][j-1]+num[i-1][j])%mod; } qu.clear(); } int main() { int i,j; scanf("%d%d%d",&n,&q,&k); for(i=0;i<=n+5;i++) c[0][i]=1; for(i=1;i<k;i++) { c[i][0]=1; for(j=1;j<=n;j++) { c[i][j]=c[i-1][j]+c[i][j-1]; if(c[i][j]>=mod) c[i][j]-=mod; } } int len=sqrt(n*k); for(i=1;i<=q;i++) { int tag; scanf("%d",&tag); if(tag==0) { int x; long long y; scanf("%d%lld",&x,&y); num[0][x]+=y; qu.push_back(node(x,y)); } else { int x; scanf("%d",&x); long long ans=num[k][x]; for(auto a:qu) { int x1=a.x; if(x1>x) continue; long long y=a.y; ans=(ans+c[k-1][x-x1]*y%mod)%mod; } printf("%lld\n",ans); } if(i%len==0) init(); } return 0; }
View Code
版权声明：本文为Hetui原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。