牛客IOI周赛21-提高组

比赛链接：https://ac.nowcoder.com/acm/contest/9798#question

题号	标题	已通过代码	通过率	我的状态
A	序列问题	点击查看	34/406	通过
B	俄罗斯方块	点击查看	19/406	通过
C	旅行没有商问题	点击查看	20/96	未通过

A

推式子题，主要是细节特别多。讨论 (q) 的范围，分 5 类。

只需 (B_{min}-A_{max} geq q)

令 (i=A_{max},j=B_{min}) , 考虑枚举 (i,j),则 (A,B) 集合中的其他数分别在 ([1,i-1],[j+1,n]) 中任取。

易得：

[ans=sum _{i=1}^{n} 2^{i-1} imes sum_{j=max{i+q,1}}^{n} 2^{n-j} ]

由于此式不能优美地化简，对 (q) 分类。

$q geq n $ 时, (ans=0).
(q in [0,n-1]) 时，

[ans=sum _{i=1}^{n-q} 2^{i-1} imes sum_{j=i+q}^{n} 2^{n-j} ]

[= sum _{i=1}^{n-q} 2^{i-1} imes (2^{n-i-q+1}-1) ]

[= (n-q-1) imes 2^{n-q} +1 ]
(qin [-n+1,-1]) 时，有两类，别漏了第二类。

[ans=sum _{i=|q|+1}^{n} 2^{i-1} imes sum_{j=i+q}^{n} 2^{n-j}+sum _{i=1}^{|q|} 2^{i-1} imes sum_{j=1}^{n} 2^{n-j} ]

[= sum _{i=|q|+1}^{n-q} 2^{i-1} imes (2^{n-i-q+1}-1)+(2^{|q|}-1) imes (2^n-1) ]

[=(n-|q|) imes 2^{n+|q|}-2^n+2^{|q|}+(2^{|q|}-1) imes (2^n-1) ]
(q leq -n) 时，随便选 (ans=(2^n-1)^2)

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const LL MOD=998244353;

LL fpow(LL x,LL k,LL MOD)
{
	LL res=1; x%=MOD;
	while(k) {
		if(k&1) res=res*x%MOD;
		x=x*x%MOD; k>>=1;
	}
	return res;
}

int T;
LL n,q;

int main()
{
//	freopen("1.in","r",stdin);

	scanf("%d",&T);
	while(T--) {
		scanf("%lld%lld",&n,&q);
		if(q>=n) printf("0
"); 
		else if(q>=0) printf("%lld
",((n-q-1)%MOD*fpow(2,n-q,MOD)%MOD+1+MOD)%MOD);
		else if(n+q<=0) printf("%lld
",(fpow(2,n,MOD)-1)*(fpow(2,n,MOD)-1)%MOD);
		else if(q<0) printf("%lld
",
			(((n+q)%MOD*fpow(2,n-q,MOD)%MOD-fpow(2,n,MOD)+fpow(2,-q,MOD))%MOD+
				(fpow(2,-q,MOD)-1)*(fpow(2,n,MOD)-1)%MOD+MOD)%MOD);
	}
	return 0;
}

B

B 是大模拟，类似于玛雅游戏。

type=1 有 2 类，type=2 有 1 类，type=3 有4类。

我不太想写，于是写一类交一次。

最后，我只考虑了 6 类就 A 了。

~~数据太水~~。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=11,INF=0x3f3f3f3f;

struct State
{
	int a[N][N];
	int tot;
	State() { memset(a,0,sizeof a); tot=0; }
	int get_height(int x)
	{
		for(int j=7;j>=1;j--) 
			if(a[j][x]) return j;
		return 0;
	}
	void suit()
	{
		int i,j,flag,k;
		for(i=7;i>=1;i--) {
			flag=0;
			for(j=1;j<=6;j++) 
				if(a[i][j]) flag++;
			
			if(flag==6) {
				for(k=i;k<=7;k++) {
					for(j=1;j<=6;j++) {
						a[k][j]=a[k+1][j];
					}
				}
				tot++;
				suit();
				return;
			}
		}
	}
	
	void print() const
	{
		puts("===========================");
		int i,j;
		for(i=7;i>=1;i--,printf("
")) 
			for(j=1;j<=6;j++)
				printf("%d ",a[i][j]);
		puts("===========================");
	}
};

int n;
int type[N];
int ans;

void dfs(int step,State s)
{
//	s.print();
	if(step==n+1) {
		ans=max(ans,s.tot);
		return;
	}
	
	int i,j,h;
	State v;
	
	if(type[step]==1) {
		// 横着放。 
		for(i=0;i<3;i++) {
			v=s;
			h=0;
			for(j=1;j<=4;j++) 
				h=max(h,v.get_height(i+j));
			
			if(h+1<=7) {
				for(j=1;j<=4;j++) 
					v.a[h+1][i+j]=1;
				v.suit();
				dfs(step+1,v);
			}
		}
		// 竖着放。 
		for(i=1;i<=6;i++) {
			v=s;
			h=v.get_height(i);
			
			if(h+4<=7) {
				for(j=1;j<=4;j++) v.a[h+j][i]=1;
//				v.print();
				v.suit();
//				v.print();
				dfs(step+1,v);
			}
		}
	}
	
	else if(type[step]==2) {
		for(i=0;i<5;i++) {
			v=s;
			h=0;
			for(j=1;j<=2;j++) {
				h=max(h,v.get_height(i+j));
			}
			if(h+2<=7) {
//				v.print();
				for(j=1;j<=2;j++)
					v.a[h+1][i+j]=v.a[h+2][i+j]=1;
//				v.print();
				v.suit();
//				v.print();
				dfs(step+1,v);
			} 
		}
	}
	
	else if(type[step]==3) {
		// A.
		for(i=0;i<4;i++) {
			v=s,h=0;
			
			for(j=1;j<=3;j++)
				h=max(h,v.get_height(i+j));
			
			if(h+2<=7) {
				for(j=1;j<=3;j++)
					v.a[h+1][i+j]=1;
				v.a[h+2][i+3]=1;
				
				v.suit();
				dfs(step+1,v);
			}
		}
		// B.
		for(i=0;i<5;i++) {
			v=s,h=0;
			for(j=1;j<=2;j++) {
				h=max(h,v.get_height(i+j));
			}
			
			if(h+3<=7) {
				v.a[h+1][i+1]=1;
				v.a[h+2][i+1]=1;
				v.a[h+3][i+1]=1;
				v.a[h+1][i+2]=1;
				
				v.suit();
				dfs(step+1,v);
			}
		}
		
		// C.
		// ***
		// *
		for(i=0;i<4;i++) {
			v=s; h=0;
			h=max(h,v.get_height(i+1)+1);
			h=max(h,v.get_height(i+2));
			h=max(h,v.get_height(i+3));
			
			if(h+1<=7) {
				v.a[h][i+1]=1;
				v.a[h+1][i+1]=1;
				v.a[h+1][i+2]=1;
				v.a[h+1][i+3]=1;
				
				v.suit();
				dfs(step+1,v);
			}
		}
	}

}

int main()
{
//	freopen("1.in","r",stdin);
	
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++) 
		scanf("%d",&type[i]);
	
	State s;
	dfs(1,s);
	cout<<ans<<endl;
	return 0;
}

话说输出 (n+1)/2 能获得 70pts.

其实熟悉了此类dfs，写起来也不难。

C

链接：https://ac.nowcoder.com/acm/contest/9798/C
来源：牛客网

给出n个点，m条边的无向图。满足无重边、自环，不保证连通。某人在图上依次访问d个节点（即所经过的所有节点构成的序列长度为d）。n个点中有k个点必须至少经过一次。起点、终点任选。求满足条件的方案数对109+7取模的值

想了一个状压，然后用矩乘优化，80pts.

#include<queue>
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=20+1;
const LL MOD=1e9+7;

int n,m,day,city;

LL f[N][64],g[N][64];
// f[i][j][k] 表示 经过了 i 个城市，现在在 j , 经过想要城市的点集为 k 的方案数。 
int a[N];
int w[N][N];

void solve()
{
	int i,j,k,u,v;
	for(i=0;i<n;i++) {
		if(~a[i]) f[i][1<<a[i]]=1;
		else f[i][0]=1;
	}
	for(i=2;i<=day;i++) {
//		for(k=0;k<(1<<city);k++)
//			for(j=0;j<n;j++)
//				printf("f[%d][%d] = %lld
",j,k,f[j][k]);
		memcpy(g,f,sizeof g);
		memset(f,0,sizeof f);
		for(k=0;k<(1<<city);k++) {
			for(j=0;j<n;j++) {
				if(~a[j] && !((k>>a[j])&1)) continue;
				
				
				if(~a[j]) {
					u=k-(1<<a[j]);
					for(v=0;v<n;v++) {
						if(~a[v] && !((u>>a[v])&1)) continue;
						if(!w[j][v]) continue;
					
						f[j][k]=(f[j][k]+g[v][u])%MOD;
					}
				} 
			
				u=k;		
				for(v=0;v<n;v++) {
					if(~a[v] && !((u>>a[v])&1)) continue;
					if(!w[j][v]) continue;
				
					f[j][k]=(f[j][k]+g[v][u])%MOD;
				}
			}
		}
		

	}
	
	LL ans=0;
	for(i=0;i<n;i++)
		ans=(ans+f[i][(1<<city)-1])%MOD;
	printf("%lld
",ans%MOD);	
}

int get(int x,int y) { return x*(1<<city)+y+1; }

struct Matrix 
{
	LL a[2000][2000];
	int n,m;
	Matrix(int n=0,int m=0) : n(n),m(m) {
		memset(a,0,sizeof a);
	}
};

Matrix mul(const Matrix &x,const Matrix &y)
{
	Matrix z;
	z.n=x.n,z.m=y.m;
	int i,j,k;
	for(i=1;i<=z.n;i++) {
		for(j=1;j<=z.m;j++) {
			for(k=1;k<=y.n;k++) 
				z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%MOD)%MOD;
		}
	}
	return z;
}

Matrix fpow(Matrix x,LL k,Matrix res)
{
	while(k) {
		if(k&1) res=mul(x,res);
		x=mul(x,x); k>>=1;
	}
	return res;
}

void print(Matrix x)
{
	for(int i=1;i<=x.n;i++,printf("
"))
		for(int j=1;j<=x.m;j++) 
			printf("%lld ",x.a[i][j]);
	printf("
");
}

void Work()
{
	int i,j,k,u,v;
	const int S=(1<<city);
	const int Row=get(n-1,S);
	Matrix A(Row,1);
	Matrix C(Row,Row);
	
	for(i=0;i<n;i++) {
		if(~a[i]) A.a[get(i,1<<a[i])][1]=1;
		else A.a[get(i,0)][1]=1;
	}
//	print(A);
	for(k=0;k<(1<<city);k++) {
		for(j=0;j<n;j++) {
			if(~a[j] && !((k>>a[j])&1)) continue;
			
			if(~a[j]) {
				u=k-(1<<a[j]);
				for(v=0;v<n;v++) {
					if(~a[v] && !((u>>a[v])&1)) continue;
					if(!w[j][v]) continue;

					C.a[get(j,k)][get(v,u)]++;
				}
			} 
		
			u=k;		
			for(v=0;v<n;v++) {
				if(~a[v] && !((u>>a[v])&1)) continue;
				if(!w[j][v]) continue;
			
				C.a[get(j,k)][get(v,u)]++;
			}
//			print(C);
		}
	}
	A=fpow(C,day-1,A);
//	print(C);
//	print(A);
	LL ans=0;
	for(i=0;i<n;i++)
		ans=(ans+A.a[get(i,(1<<city)-1)][1])%MOD;
	printf("%lld
",ans%MOD);	
}

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	int x,y;
	
	cin>>n>>m>>day>>city;
	memset(a,-1,sizeof a);
	for(i=0;i<city;i++) {
		cin>>x;
		x--;
		a[x]=i;
	}
	for(i=1;i<=m;i++) {
		cin>>x>>y;
		x--,y--;
		w[x][y]=w[y][x]=1;
	}
	
//	if(day<=1000 || n<=5) solve();
	Work();
	return 0;
}

正解咕咕咕中。

Update 2021.2.6：

考虑容斥。

对不选的点容斥即可。

#include<queue>
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=20+1;
const LL MOD=1e9+7;

int n,m,day,city;
int w[N][N],a[N];

struct Matrix 
{
	LL a[N][N];
	int n,m;
	Matrix(int n=0,int m=0) : n(n),m(m) {
		memset(a,0,sizeof a);
	}
};

Matrix mul(const Matrix &x,const Matrix &y)
{
	Matrix z;
	z.n=x.n,z.m=y.m;
	int i,j,k;
	for(i=1;i<=z.n;i++) {
		for(j=1;j<=z.m;j++) {
			for(k=1;k<=y.n;k++) 
				z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%MOD)%MOD;
		}
	}
	return z;
}

Matrix fpow(Matrix x,LL k,Matrix res)
{
	while(k) {
		if(k&1) res=mul(x,res);
		x=mul(x,x); k>>=1;
	}
	return res;
}

void print(Matrix x)
{
	for(int i=1;i<=x.n;i++,printf("
"))
		for(int j=1;j<=x.m;j++) 
			printf("%lld ",x.a[i][j]);
	printf("
");
}

int main()
{
//	freopen("1.in","r",stdin);
	int i,j,k;
	int x,y;
	
	cin>>n>>m>>day>>city;
	Matrix C(n,n),B(n,n),A(n,1),D(n,1);
	for(i=0;i<city;i++) 
		cin>>a[i];
	for(i=1;i<=m;i++) {
		cin>>x>>y;
		C.a[x][y]=C.a[y][x]=1;
	}

	for(i=1;i<=n;i++) D.a[i][1]=1;
	LL ans=0;
	for(i=0;i<(1<<city);i++) {
		B=C,A=D;
		int sign=1;
		for(j=0;j<city;j++) { // 容斥，不经过哪些点。 
			if((i>>j)&1) {
				sign=-sign;
				for(k=1;k<=n;k++) 
					B.a[a[j]][k]=B.a[k][a[j]]=0;
				A.a[a[j]][1]=0;
			}
		} 
		A=fpow(B,day-1,A);
		for(j=1;j<=n;j++) 
			ans=(ans+A.a[j][1]*sign)%MOD;
	}
	
	ans=(ans+MOD)%MOD;
	printf("%lld
",ans);
	return 0;
}

遇到不经过比经过好做的，一定要想到容斥。

时间复杂度：(O(2^kn^3logd))

感谢 @DoMoRanSky 巨巨的指点。