[省选集训2022] 模拟赛13

未来

题目描述

给你一个长度为 \(n\) 的环状数组，每个位置有三种颜色：红、绿、蓝。

有 \(m\) 次操作，每次操作形如：对于所有位置 \(x\)，如果位置 \(x\) 和位置 \(x+1\bmod n\) 颜色相同，那么位置 \(x\) 颜色不变；否则位置 \(x\) 变为这两个位置上没有出现过的颜色。注意变化是同时进行的。

问操作 \(m\) 次之后得到的颜色数组是什么？

\(2\leq n\leq 5\cdot 10^5,0\leq m\leq 10^{18}\)

解法

考虑把颜色分别分别改写成 \(0,1,2\)，不难发现操作等价于 \(a_i'\leftarrow -a_i-a_{i+1\bmod n}\bmod 3\)

所以显然的思路是多项式倍增，把 \((-1-x^{n-1})^m\bmod (x^n-1)\) 这东西算出来，然后和初始数组卷积即可（本质上就是算贡献，多项式是初始状态和最终状态之间的桥梁）

这样已经能获得大部分的分数，进一步的优化就考虑 \((-1-x^{n-1})^{3^k}\bmod 3=-1-x^{-3^k}\)，这是因为，根据 \(\tt lucas\) 定理，其他的项都是 \(3\) 的倍数会被模掉，那么我们把 \(m\) 拆位之后分别做即可，时间复杂度 \(O(n\log m)\)

其实跟是一样的，没什么意思。

#pragma GCC optimize("Ofast")
#include 
#include 
using namespace std;
const int M = 500005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,a[M],b[M];char s[M];
signed main()
{
	freopen("future.in","r",stdin);
	freopen("future.out","w",stdout);
	n=read();m=read();scanf("%s",s);
	for(int i=0;i=s)
		{
			for(int i=0;i

回忆

题目描述

\(n\times m\) 大小的矩阵，每个位置有值 \(a_{i,j}\)，表示这个格子可能开放的概率，求最大四联通块的期望，模 \(998244353\)

\(n\times m\leq 40\)

解法

使用连通性状压的时候要勇敢一点，仅此而已。

假设 \(n，我们考虑逐列递推，发现需要记录的状态只有：连通性的最小表示法,每个位置的连通块大小,历史最大连通块 这些状态，那么把它们打包放进 \(\tt vector\) 中，然后套上 \(\tt map\) 转移即可。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 45;
const int MOD = 998244353;
#define x first
#define y second
#define vii vector
#define node pair
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,fa[10],a[M][M],b[M][M];map f[2];
void add(int &x,int y) {x=(x+y)%MOD;}
int find(int x)
{
	while(x!=fa[x]) x=fa[x];
	return x;
}
node operator + (node u,int s)
{
	int cnt=0,use[10]={};
	for(int i=0;i<10;i++) fa[i]=i;
	node r;r.x.resize(n);
	for(int i=0;i>i&1)
	{
		if(s>>i>>1&1) fa[find(i+1)]=find(i);
		if(u.x[i])
		{
			for(int j=i+1;j>j&1) && u.x[i]==u.x[j])
					fa[find(j)]=find(i);
		}
	}
	for(int i=0;i>i&1) && find(i)==i) r.x[i]=++cnt;
	for(int i=0;i>i&1) r.x[i]=r.x[find(i)];
	r.y.resize(cnt+1);
	for(int i=0;i>i&1)
	{
		if(u.x[i] && !use[u.x[i]])
			r.y[r.x[i]]+=u.y[u.x[i]],use[u.x[i]]=1;
		r.y[r.x[i]]++;
	}
	r.y[0]=u.y[0];
	for(int i=1;i<=cnt;i++)
		r.y[0]=max(r.y[0],r.y[i]);
	return r;
}
signed main()
{
	freopen("memory.in","r",stdin);
	freopen("memory.out","w",stdout);
	n=read();m=read();
	for(int i=0;im)//flip and reverse
	{
		for(int i=0;i>j&1) p=1ll*p*a[j][i]%MOD;
				else p=1ll*p*(MOD+1-a[j][i])%MOD;
			}
			if(!p) continue;
			for(auto &u:f[w^1])
				add(f[w][u.x+s],1ll*u.y*p%MOD);
		}
	}
	for(auto &u:f[w]) add(ans,1ll*u.y*u.x.y[0]%MOD);
	printf("%d\n",ans);
}
数学-多项式dp-状压dp

相关

标签