Logo __vector__ 的博客

博客

ABC418F 题解

...
__vector__
2025-12-01 12:56:05

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-11 09:44:06

题意

给定一个长度为 $n$ 的整数数组 $a$，下标从 $1$ 编号到 $n$。

有一个 $1 \times n$ 的网格图，每个格子要么放茶，要么放咖啡，有以下两个条件：

  1. 任意两个相邻格子，至少要有一个格子放茶。
  2. 对于任意 $i$，使得 $a_i \neq -1$，那么前 $i$ 个格子强制恰好有 $a_i$ 个格子放咖啡。

求有多少种合法的摆放方案。

分析性质

任意两个相邻格子，至少要有一个格子放茶。

这个条件等价于：任意两个放咖啡的格子不能相邻。

对于第二个条件，本质上，将一段前缀的格子划分成了若干个区间，每个区间的咖啡数量是确定的，剩下一段后缀的咖啡数量则不确定。

暴力做法

考虑左到右有 $m$ 个格子，且咖啡数量确定为 $k$，那么方案数是多少。

这个问题可以转化为在 $m$ 个连续位置里面选择 $k$ 个两两不相邻的位置的方案数。

再次转化，发现这个问题等价于有 $m-k$ 个物品，需要选择 $k$ 个这些物品的间隙，分别插入一个新的物品，那么方案数就是 $\binom{m-k+1}{k}$。

为了简化表示，令上述问题的答案为 $g(m,k)$。

首先，仅考虑已经确定咖啡总数的那些区间。

假设第 $i$ 个区间的长度为 $l_i$，咖啡数量为 $x_i$。

那么设计出状态 $f_{i,0/1}$ 表示前 $i$ 个区间已经确定，且最后一个区间的最后一个位置是否为咖啡，那么总合法方案数是多少。

考虑状态转移，以下默认每种转移的结果都累加。

  1. 上一个区间的末尾没有咖啡，这次的区间末尾也没有咖啡。
    $f_{i,0} \leftarrow f_{i-1,0} \cdot g(l_i-1,x_i)$。
  2. 上一个区间的末尾有咖啡，这次的区间末尾没有咖啡。
    此时分类讨论两种情况。
    • 若 $l_i \ge 2$。
      $f_{i,0} \leftarrow f_{i-1,1} \cdot g(l_i-2,x_i)$。
    • 若 $l_i = 1$。
      $f_{i,0} \leftarrow [x=0]$。
  3. 上一个区间的末尾没有咖啡，这次的区间末尾有咖啡。
    • 若 $l_i \ge 2$。
      $f_{i,1} \leftarrow f_{i-1,0}\cdot g(l_i-2,x_i-1)$。
    • 若 $l_i = 1$。
      $f_{i,1} \leftarrow [x=1]$。
  4. 上一个区间的末尾有咖啡，这次区间的末尾也有咖啡。
    • 若 $l_i \ge 3$。
      $f_{i,1} \leftarrow f_{i-1,1} \cdot g(l_i-3,x_i-1)$。
    • 若 $l_i = 2$。
      $f_{i,1} \leftarrow [x=1]$。
    • 若 $l_i = 1$。
      无解。

上述 DP 解决了由已经确定总咖啡数量的区间组成的那一段前缀。

但是还剩下一段后缀，没有咖啡数量限制，仅被咖啡不能相邻的条件约束。

如果设计出一种新的 DP 解决这一部分，会比较麻烦，考虑复用之前的 DP。

一种比较简单的方法，可以将剩下的那一段后缀划分为若干个单个元素组成的区间，沿用原来的 DP 状态。

对于状态转移，则枚举当前区间有一个咖啡还是有零个咖啡，分别按照之前的转移方式算出结果，加起来就是总方案数。

现在，成功构造出了一种单次 $O(n)$ 的做法。

优化

每次修改，都是修改某位置的前缀和。

注意到，它实际上最多影响两个区间的总和。

另外注意到，原来的 DP 状态，完全可以写成矩阵的形式，通过矩阵乘法转移，这样就支持了线段树快速合并答案。

现在最大的问题，在于每次操作都可能增加一个区间，或删除一个区间，这样就没法直接维护每个区间的答案。

但这个也是可以简单解决的。

首先开一个 set 维护所有存在的区间。

对于每个区间，可以只在其中一个位置维护其整个区间的转移矩阵，区间其他位置全部填充为单位矩阵。

每次修改，都将可能影响的两个区间全部填充为单位矩阵，然后重新填就行了。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const ll mod=998244353;
const int maxn=2e5+5;
int n,q;
struct Matrix{
	ll mat[2][2];
	void init(){
		memset(mat,0,sizeof mat);
	}
	void unit(){
		init();
		mat[0][0]=mat[1][1]=1;
	}
	Matrix operator*(const Matrix& b)const{
		Matrix res;
		res.init();
		FOR(i,0,1){
			FOR(k,0,1){
				FOR(j,0,1){
					(res.mat[i][j]+=mat[i][k]*b.mat[k][j])%=mod;
				}
			}
		}
		return res;
	}
	Matrix operator+(const Matrix& b)const{
		Matrix res;
		FOR(i,0,1){
			FOR(j,0,1){
				(res.mat[i][j]=mat[i][j]+b.mat[i][j])%=mod;
			}
		}
		return res;
	}
};
struct SGT{
	int lef[maxn<<2],rig[maxn<<2];
	Matrix res[maxn<<2],cov[maxn<<2];
	bool tag[maxn<<2];\/\/ 本节点存在 lazytag
	void pushup(int pos){
		res[pos]=res[pos<<1]*res[pos<<1|1];
	}
	void upd(int pos,Matrix _cov,bool _tag){
		tag[pos]=_tag;
		cov[pos]=_cov;
		res[pos]=_cov;
		\/\/ 理论上应该是 qpow(_cov,r-l+1)
		\/\/ 但是，赋值要么是单位矩阵，要么是区间长度为 1
	}
	void pushdown(int pos){
		if(!tag[pos])return;
		upd(pos<<1,cov[pos],tag[pos]);
		upd(pos<<1|1,cov[pos],tag[pos]);
		tag[pos]=0;
	}
	void bd(int pos,int l,int r){
		lef[pos]=l,rig[pos]=r,res[pos].unit(),tag[pos]=0;
		if(l==r)return;
		int mid=(l+r>>1);
		bd(pos<<1,l,mid);
		bd(pos<<1|1,mid+1,r);
	}
	void chg(int pos,int l,int r,Matrix _cov){
		if(lef[pos]>=l&&rig[pos]<=r){
			upd(pos,_cov,1);
			return;
		}
	\/\/	printf("pos %d\n",pos);
		pushdown(pos);
		int mid=(lef[pos]+rig[pos]>>1);
		if(mid>=l)chg(pos<<1,l,r,_cov);
		if(mid<r)chg(pos<<1|1,l,r,_cov);
		pushup(pos);
	}
}sgt;
ll qpow(ll a,ll b){
	ll ret=1;
	for(;b;a=a*a%mod,b>>=1){
		if(b&1)ret=ret*a%mod;
	}
	return ret;
}
ll inv(ll a){
	return qpow(a,mod-2);
}
ll fact[maxn*2],factinv[maxn*2];
ll C(int n,int m){
\/\/	printf("C(%d,%d) = %lld\n",n,m,((n>=m)?fact[n]*factinv[m]%mod*factinv[n-m]%mod:0));
	return ((n>=m)?fact[n]*factinv[m]%mod*factinv[n-m]%mod:0);
}
ll F(int len,int x){
	if(len<0||x<0)return 0;
	return C(len-x+1,x);
}
Matrix calc(int len,int x){
	Matrix res;
	res.init();
	\/\/ 原来末尾没有，现在末尾没有
	{
		res.mat[0][0]=F(len-1,x);
	}
	\/\/ 原来末尾有，现在末尾没有
	{
		if(len>=2){
			res.mat[1][0]=F(len-2,x);
		}else{
			\/\/ 第一个排除位置，与最后一个排除位置重合，实际只关心唯一一个位置是否不填
			res.mat[1][0]=(x==0);
		}
	}
	\/\/ 原来末尾没有，现在末尾有
	{
		if(len>=2){
			res.mat[0][1]=F(len-2,x-1);
		}else{
			res.mat[0][1]=(x==1);	
		}
	}
	\/\/ 原来末尾有，现在末尾有
	{
		if(len>=3){
			res.mat[1][1]=F(len-3,x-1);
		}else{
			res.mat[1][1]=(len==2&&x==1);
		}
		
	}
	return res;
}
set<int> poslist; 
int pre[maxn];
Matrix ways_nolim[maxn];\/\/ 没有咖啡数量的限制，仅有咖啡不能相邻的限制
Matrix unitmat;
void print(){
	Matrix ans;
	ans.init();
	ans.mat[0][0]=1;
	ans=ans*sgt.res[1];
	auto ptr=prev(poslist.end());
	ans=ans*ways_nolim[n-*ptr];
	printf("%lld\n",((ans.mat[0][0]+ans.mat[0][1])%mod+mod)%mod);
}
void solve(int id_of_test){
	read(n);
	read(q);
	vector<pii> queries;
	FOR(i,1,q){
		int x,y;
		read(x);
		read(y);
		queries.eb(mkpr(x,y));
	}
	sgt.bd(1,1,n);
	poslist.insert(0);
\/\/	print();
\/\/	printf("ways_no_lim %lld %lld\n",ways_nolim[n].mat[0][0],ways_nolim[n].mat[0][1]);
\/\/	return;
	for(auto [pos,_val]:queries){
		if(pre[pos]==_val){
			print();			
			continue;
		}
		if(pre[pos]==-1){
			\/\/ 增加新的右端点
			pre[pos]=_val;
			auto _rg=poslist.lower_bound(pos);
			auto _lf=_rg;
			_lf--;
			int lf=*_lf+1,rg;
			sgt.chg(1,lf,pos,unitmat);\/\/ 删除 [lf,pos]
			if(_rg!=poslist.end()){
				rg=*_rg;
				{
					\/\/ [lf,rg] 是原来 pos 所在的完整区间
					\/\/ 首先删除原来区间		 
					sgt.chg(1,lf,rg,unitmat);
				}
				if(pos!=rg){
					\/\/ 加入 [pos+1,rg]
					sgt.chg(1,pos+1,pos+1,calc(rg-(pos+1)+1,pre[rg]-pre[pos]));
				}
			}
			\/\/ 加入 [lf,pos]
			sgt.chg(1,lf,lf,calc(pos-lf+1,pre[pos]-pre[lf-1]));
			poslist.insert(pos);
		}else if(_val==-1){
			\/\/ 减少一个右端点
			pre[pos]=-1;
			auto _rg=poslist.find(pos);
			auto _lf=_rg;
			_lf--;
			_rg++;
			int lf=*_lf+1;
			int rg;
			sgt.chg(1,lf,pos,unitmat);
			if(_rg!=poslist.end()){\/\/ 存在下一个右端点，提供合并
				rg=*_rg;
				\/\/ 删除原来区间
				sgt.chg(1,lf,rg,unitmat);
				\/\/ 加入新的
				if(pre[rg]!=-1)sgt.chg(1,lf,lf,calc(rg-lf+1,pre[rg]-pre[lf-1]));
			}else{
				sgt.chg(1,lf,n,unitmat);\/\/ 否则，后面整段都没了。
			}
			poslist.erase(pos);
		}else{
			\/\/ 简单地修改值
			pre[pos]=_val;
			auto _rg=poslist.find(pos);
			auto _lf=_rg;
			_lf--;
			_rg++;
			int lf=*_lf+1;
			int rg;
			sgt.chg(1,lf,pos,unitmat);
			if(_rg!=poslist.end()){
				rg=*_rg;
				sgt.chg(1,lf,rg,unitmat);
				if(pre[rg]!=-1)sgt.chg(1,rg,rg,calc(rg-(pos+1)+1,pre[rg]-pre[pos]));
			}
			sgt.chg(1,lf,lf,calc(pos-lf+1,pre[pos]-pre[lf-1]));
		}
		print();
	}
}
int main()
{
	unitmat.unit();
	fact[0]=1;
	FOR(i,1,maxn*2-1)fact[i]=fact[i-1]*i%mod;
	factinv[maxn*2-1]=inv(fact[maxn*2-1]);
	REP(i,maxn*2-1,1)factinv[i-1]=factinv[i]*i%mod;
	ways_nolim[0].unit();
	auto sgway=calc(1,0)+calc(1,1);
\/\/	return 0;
	FOR(i,1,maxn-1){
		ways_nolim[i]=ways_nolim[i-1]*sgway;
	}
	FOR(i,1,maxn-1){
		pre[i]=-1;
	}
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
\/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*\/

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

服务器时间: 2025-12-15 04:17:40 | 开源项目