列表

详情

NC232413. Painting Fences

描述

你要粉刷一段栅栏。栅栏的长度为 n，分为 n 段长度为 1 的格子，编号为 。每一个格子被粉刷颜色必须相同。共有 m 种颜色，编号为 。设第 i 个格子内刷颜色 a_i。

定义 为一个极长颜色连续段，当且仅当同时满足：

- 第 个格子内的颜色相同；
- 或 ；
- 或 。

你会随机粉刷每一个栅栏的格子（即，对于每个格子，等概率随机染它目前可以染的颜色）。你想知道极长颜色连续段个数的期望对 998244353 取模的值。

可难满足的栅栏主人提出了一些要求。有 q 次操作，每次加入一条限制「a_x 不能是 y」，或删除一条限制。你需要在每次操作后求出答案。

输入描述

第一行是三个正整数 n,m,q。

接下来 q 行，每行为以下两种：

- `1 x y` 加入限制「a_x 不能是 y」。保证这次操作之前，a_x 可以是 y。
- `2 id` 取消第 id 个操作的限制（下标从 1 开始，取消的操作保证是第一种类型的操作）。

对于所有数据，，，，保证任意时刻至少有一种合法方案。

输出描述

 行，对初始状态、每个操作后的状态分别输出答案对 998244353 取模的值。

示例1

输入: 

4 2 5
1 2 1
1 1 1
1 3 2
2 2
1 4 2

输出: 

499122179
499122179
2
499122179
3
499122179

说明:

- 在所有操作之前的方案：1111,1112,1121,1122,1211,1212,1221,1222,2111,2112,2121,2122,2211,2212,2221,2222，答案等于 \dfrac{2\times 1+6\times 2+6\times 3+2\times 4}{16}=\dfrac{5}{2}。
- 在第一次操作之后的方案：1211,1212,1221,1222,2211,2212,2221,2222，答案等于 \dfrac{1\times 1+3\times 2+3\times 3+1\times 4}{8}=\dfrac{5}{2}。
- 在第二次操作之后的方案：2211,2212,2221,2222，答案等于 \dfrac{1\times 1+2\times 2+1\times 3}{4}=2。
- 在第三次操作之后的方案：2211,2212，答案等于 \dfrac{1\times 2+1\times 3}{2}=\dfrac{5}{2}。
- 在第四次操作之后的方案：1211,1212,2211,2212，答案等于 \dfrac{1\times 2+2\times 3+1\times 4}{4}=3。
- 在第五次操作之后的方案：1211,2211，答案等于 \dfrac{1\times 2+1\times 3}{2}=\dfrac{5}{2}。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 1641ms, 内存消耗: 60956K, 提交时间: 2022-01-20 22:18:59 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353
int i,j,k,n,m,t,x,y,ty;
int op1[300500],op2[300500];
ll a[300500],b[300500],res;
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
int su(ll a,ll b){a+=b;return (a>=M)?a-M:a;}
map<int,int> mp[300500];
void add(int l,int r,int op){
	if(x<1||r>n)return;
	ll sum=a[l]*a[r]%M,sb;
	sb=su(sum,M-b[l])*ksm(sum,M-2)%M;
	res=su(res,(op>0)?sb:M-sb);
}
int main() {
	ios::sync_with_stdio(0);
	cin>>n>>m>>t;
	for(i=1;i<=n;i++)a[i]=b[i]=m;
	res=1+1ll*(n-1)*(m-1)%M*ksm(m,M-2)%M;
	cout<<res<<'\n';
	for(int T=1;T<=t;T++){
		cin>>ty;
		if(ty==1){
			cin>>x>>y;
			op1[T]=x;op2[T]=y;
			add(x-1,x,-1);add(x,x+1,-1);
			a[x]--;mp[x][y]=1;
			if(x>1&&!mp[x-1][y]){b[x-1]--;}
			if(x<n&&!mp[x+1][y]){b[x]--;}
			add(x-1,x,1);add(x,x+1,1);
		}
		else{
			cin>>k;
			x=op1[k];y=op2[k];
			add(x-1,x,-1);
			add(x,x+1,-1);
			a[x]++;mp[x][y]=0;
			if(x>1&&!mp[x-1][y])b[x-1]++;
			if(x<n&&!mp[x+1][y])b[x]++;
			add(x-1,x,1);add(x,x+1,1);
		}
		cout<<res<<'\n';
	}
}

上一题

© 2024 nowcoder.com