【学习笔记】AGC046

C - Shift

首先问题转化为给定一个串$t$问$s$经过最少多少步能变成$t$

然后考虑逆向操作每次相当于把一个$0$前面的$1$移动到后面去

记$c_i$表示第$i$个$0$和第$i+1$个$0$之间的$1$的数目显然两个串相同等价于 { c i } \{c_i\} {ci​}相同并且每次操作相当于选择$i<j$使得$c_i$减$1$$c_j$加$1$

记$s_i=\sum a_i$显然答案是$\sum \max (0,c_i-c_i^{\prime })$并且对任意$i$满足$s_i\ge s_i^{\prime }$。

注意两维的大小都是$n$如果暴力转移那么复杂度似乎是$O(n^4)$。

事实上跑不满。使用部分和可以优化到$O(n^3)$。

复杂度都不会算是不是该退役了

能过的代码为什么要优化呀

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db long double
#define cpx complex<db>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=998244353;
string s;
int n,m,K,a[305],f[305][305],g[305][305],one,res;
void add(int &x,int y){
	if((x+=y)>=mod)x-=mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s>>K,n=s.size();
    for(int i=0;i<n;i++){
    	if(s[i]=='0'){
    		m++;for(int j=i-1;j>=0;j--){
    			if(s[j]=='1')a[m]++;
    			else break;
			}
    		one+=a[m];
		}
	}m++;for(int i=n-1;i>=0;i--){
		if(s[i]=='1')a[m]++;
		else break;
	}one+=a[m];
	int s=0;f[0][0]=1;
	for(int i=1;i<=m;i++){
		memset(g,0,sizeof g);
		for(int j=s;j<=one;j++){
			for(int k=0;k<=j;k++){
				if(!f[j][k])continue;
				for(int l=0;l<=one-j;l++){
					add(g[j+l][k+max(0,l-a[i])],f[j][k]);
				}
			}
		}memcpy(f,g,sizeof g),s+=a[i];
	}for(int i=0;i<=min(one,K);i++)add(res,f[one][i]);
	cout<<res;
}

D - Secret Passage

首先考虑长度为$m$的串$t$能否被生成。考虑逆向操作每次相当于选一个数放到开头然后在开头放$0/1$。那么考虑没被操作过的位置肯定构成了$s$的后缀被操作的位置可以按任意顺序排列那么只要判一下$0/1$的数目。

设$f_{i,j,k}$表示生成了长度为$i$的后缀其中匹配的长度是$j$未匹配的位置中$1$的个数是$k$的方案数。大力转移即可。

诶怎么一直wa???

仔细思考 wa了半天 后发现构造并没有那么简单但是我们发现此时正着非常好做因为插到后面就不用管了这里有一个非常巧妙的观察第一次显然对前两个数进行操作如果剩下的那个数没有放在后面那么它在以后的操作中也不会被放在后面设$h_{i,j,k}$表示前缀$i$位生成了$j$个$0$$k$个$1$时可以被任意放置的数的最大值可以$O(1)$转移。

复杂度$O(n^3)$。

细节很多比较难受

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db long double
#define cpx complex<db>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=998244353;
int n,a[305],b[305],f[305][305],g[305][305],h[305][305][305],res;
char s[305];
void add(int &x,int y){
	if((x+=y)>=mod)x-=mod;
}
void chmax(int &x,int y){
	x=max(x,y);
}
signed main(){
    scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++)a[i]=(s[i]=='1'),b[i]=b[i-1]+a[i];
	memset(h,-1,sizeof h);h[0][0][0]=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<=i;k++){
				if(h[i][j][k]==-1)continue;
				if(a[i+1])chmax(h[i+1][j+1][k],h[i][j][k]-1);
				if(!a[i+1])chmax(h[i+1][j][k+1],h[i][j][k]-1);
				chmax(h[i+1][j][k],h[i][j][k]);
				if(i+2<=n){
					chmax(h[i+2][j][k],h[i][j][k]+1);
					if(a[i+1]||a[i+2])chmax(h[i+2][j+1][k],h[i][j][k]);
					if(!a[i+1]||!a[i+2])chmax(h[i+2][j][k+1],h[i][j][k]);
				}
			}
		}
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		memset(g,0,sizeof g);
		for(int j=0;j<i;j++){
			for(int k=0;k<i;k++){
				if(!f[j][k])continue;
				add(g[j][k+(!a[n-j])],f[j][k]);
				add(g[j+1][k],f[j][k]);
			}
		}memcpy(f,g,sizeof g);
		for(int j=0;j<=i;j++){
			for(int k=0;k<=i;k++){
				if(f[j][k]&&2*i-j<=n&&k<=b[n-j]&&i-j-k<=n-j-b[n-j]&&h[n-j][k][i-j-k]!=-1){
					add(res,f[j][k]);
				}
			}
		}
	}cout<<res;
}

E - Permutation Cover

考虑两件事
$1.1$ 如何判断是否有解。这等价于是找必要条件我们任取$i$,$j$比较它们的出现次数容易得到结论$2\min (a_i,a_j)\ge \max (a_i,a_j)$构造也非常简单让最小数$-1$其他数$-2$即可。
$1.2$ 如何求字典序最小。换句话说给定一段前缀判断是否有解。先将不足$K$的部分补完显然此时如果$2\min (a_i)\ge \max (a_i)$那么有解否则一定满足$2\min (a_i)+1=\max (a_i)$此时必须再补一个最大值在后面这样恰好有解。

复杂度$O(\sum a_i{k}^2)$。

代码很难写

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db long double
#define cpx complex<db>
#define inf 0x3f3f3f3f
using namespace std;
int K,n,m,a[1005],b[1005],s[1005],v[1005];
int check(int n){
	for(int i=1;i<=K;i++)v[i]=0;
	for(int i=n-K+1;i<=n;i++)v[s[i]]=1;
	for(int i=1;i<=K;i++)if(!v[i])return 0;
	return 1;
}
int solve(){
	int t=1;while(s[t])t++;for(int i=1;i<=K;i++)b[i]=a[i];
	for(int i=1;i<=K;i++)v[i]=0;
	for(int i=m+1;i<t;i++){
		if(v[s[i]])return 0;
		v[s[i]]=1;
	}for(int i=m+1;i<t;i++)b[s[i]]++;for(int i=1;i<=K;i++)b[i]--;
	int mi=inf,mx=0,L=0;for(int i=1;i<=K;i++)mi=min(mi,b[i]),mx=max(mx,b[i]);
	for(int i=1;i<=K;i++)if(b[i]==mx)L++;
	if(2*mi>=mx)return 1;
	if(2*mi==mx-1){
		for(int i=m+1;i<t;i++){
			if(b[s[i]]==mi)return 0;
			if(b[s[i]]==mx)L--;
			if(!L)return 1;
		}return 1;
	}for(int i=1;i<=K;i++)b[i]=a[i];
	if(m){
		for(int i=m-K+1;i<=m;i++)v[s[i]]=i-m+K;
		int l=0;for(int i=m+1;i<t;i++)l=max(l,v[s[i]]),b[s[i]]++;
		for(int i=m-K+1;i<=m-K+l;i++)b[s[i]]--;
		mi=inf,mx=0,L=0;for(int i=1;i<=K;i++)mi=min(mi,b[i]),mx=max(mx,b[i]);
		for(int i=1;i<=K;i++)if(b[i]==mx)L++;
		if(2*mi>=mx)return 1;
		if(2*mi==mx-1){
			if(l!=K){
				for(int i=m-K+l+1;i<=m;i++){
					if(b[s[i]]==mi)return 0;
					if(b[s[i]]==mx)L--;
					if(!L)return 1;
				}return 1;
			}
			else {
				for(int i=m+1;i<t;i++){
					if(b[s[i]]==mi)return 0;
					if(b[s[i]]==mx)L--;
					if(!L)return 1;
				}return 1;
			}
		}return 0;
	}for(int i=1;i<t;i++)b[s[i]]++;for(int i=1;i<=K;i++)b[i]--;	
	mi=inf,mx=0,L=0;for(int i=1;i<=K;i++)mi=min(mi,b[i]),mx=max(mx,b[i]);
	for(int i=1;i<=K;i++)if(b[i]==mx)L++;
	if(2*mi>=mx)return 1;
	if(2*mi==mx-1){
		for(int i=1;i<t;i++){
			if(b[s[i]]==mi)return 0;
			if(b[s[i]]==mx)L--;
			if(!L)return 1;
		}return 1;
	}
	return 0;
}
signed main(){
    cin>>K;for(int i=1;i<=K;i++)cin>>a[i],n+=a[i];
    if(!solve()){
    	cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++){
		int ok=0;
		for(int j=1;j<=K;j++){
			if(a[j]==0)continue;
			s[i]=j,a[j]--;
			if(solve()){
				ok=1;
				break;
			}
			a[j]++;
		}assert(ok);
		if(i>=K&&check(i))m=i;
		cout<<s[i]<<' ';
	}
}

F - Forbidden Tournament

这是道数学题。

考虑怎么判断一张图是否合法。

如果存在一个点没有入度那么把这个点删去直到每个点至少有一个入度。

我们称$H$是不好的也就是三元环都向一个点连边。

任选一个点$v$记 Y = { w ∣ v → w } Y=\{w|v\to w\} Y={w∣v→w}也就是$v$出边连向的集合$X=V\setminus Y$也就是$v$的入边加上$v$自己。

如果$X$中有环也就是有三元环首先$v$肯定不在环内那么这个环都向$v$连边就构成了$H$。

$1.1$ $X$是一个$DAG$存在一个$x_1,...,x_k$且$x_k=v$满足若$i<j$则$x_i\to x_j$。

$1.2$ 对于$u\in X$$w\in Y$如果$w\to u$且$w\to w^{\prime }$我们可以推出$w^{\prime }\to u$否则会构成$H$。

$1.3$ 如果$Y$中有环那么取$u=x_1$设环外一点$w$满足$w\to u$不难发现两种情况都会构成$H$因此$Y$是一个$DAG$存在$y_1,...,y_l$满足若$i<j$则$y_i\to y_j$。

$1.4$ 不难发现$y_l\to x_1$。我们将$y_l$提出来得到若$x_i\to y_l$那么$\forall i^{\prime }\in [i,k]$$x_{i^{\prime }}\to y_l$

$1.5$ 我们不妨取最大的$t$满足$y_l\to x_t$。设$i\in [1,t]$我们再任取一个点$y_j$若$x_i\to y_j$那么$\forall i^{\prime }\in [i,t]$$x_i^{\prime }\to y_j$。注意到$i\in [t+1,k]$时$x_i\to y_j$因此$t$的范围可以省去。

基于上述观察我们可以直接计数。设删去了$i$个入度为$0$的点那么转化为$(N-i,K-i)$规模的问题乘上系数$\left(\genfrac{}{}{0ex}{}{N}{i}\right)i!$。枚举左部点和右部点的数目问题转化为一个$k\times l$矩阵的方案数其中$a_{i,j}=1$表示$y_j\to x_i$。

我们将性质$1.2$转化成若$y_j\to x_i$那么$\forall j^{\prime }\in [j,l]$$y_j^{\prime }\to x_i$。那么结合$1.2$和$1.5$这个网格图满足

• $a_{i,j}=1\Rightarrow \forall j^{\prime }\in [j,l],a_{i,j^{\prime }}=1$
• $a_{i,j}=0\Rightarrow \forall i^{\prime }\in [i,k],a_{i^{\prime },j}=1$
• $a_{1,l}=1$
• $a_{k,j}=1$

直接对这个阶梯状矩阵计数即可。不难发现只需要判边界处的点的度数。

这一步复杂度$O(kl)$总复杂度$O(n^4)$。

似乎这道题有什么高论但是我不清楚

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db long double
#define cpx complex<db>
#define inf 0x3f3f3f3f
using namespace std;
int n,K,mod;
ll fac[205],inv[205],f[205],res;
ll pw(ll x,ll y=mod-2){
	ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
void init(int n){
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	inv[n]=pw(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(int x,int y){
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
ll calc(int n,int m,int K){
	assert(K>=n-1);
	if(m==0)return 0;
	memset(f,0,sizeof f),f[1]=1;
	for(int i=1;i<=m;i++){
		ll sm=0;
		for(int j=1;j<=n;j++){
			if(i==1&&j==n)continue;
			sm=(sm+f[j])%mod;
			if(m-i+j<=K&&i+n-j-1<=K)f[j]=sm;
			else f[j]=0;
		}
	}ll res=0;for(int i=1;i<=n;i++)res=(res+f[i])%mod;
	return res;
}
ll solve(int n,int m){
	if(n==1)return 1;
	ll res(0);
	for(int i=2;i<=m+1;i++)res=(res+calc(i,n-i,m))%mod;
	res=res*fac[n-1]%mod;
	return res;
}
signed main(){
    cin>>n>>K>>mod,init(n);
    for(int i=0;i<=K;i++){
    	res=(res+binom(n,i)*fac[i]%mod*solve(n-i,K-i))%mod;
	}
    cout<<(res+mod)%mod;
}