CH3401 石头游戏

Peaks

求n个排列中有恰好k个峰的方案数，模239

n<=10,k<=30

题解

\(f(i,j)\) 表示填了 \(1~ i\) 有 \(j\) 个峰的方案数。

那么 \(2j\cdot f(i,j) \rightarrow f(i+1,j)\)，\((i+1-2j)\cdot f(i,j) \rightarrow f(i+1,j+1)\)。

于是转移可以写成矩阵形式。考虑系数 \(i+1-2j\) 怎么处理。发现由于模数很小，所以可以利用矩阵的周期性。

k和模数的大小提示找规律，事实上当 \(k\leq 30\) 时，\(f(n,k)=f(n+56882,k)~(\bmod 239)\)

CO int mod=239;

int f[56882][31];

int main(){

	int n=read<LL>()%56882,k=read<int>();

	f[1][1]=1;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=k;++j)if(f[i][j]){

			f[i+1][j]=(f[i+1][j]+2*j*f[i][j])%mod;

			f[i+1][j+1]=(f[i+1][j+1]+(i+1-2*j)*f[i][j])%mod;

		}

	printf("%d\n",f[n][k]);

	return 0;

}

分析

由于\(\le 6\)的正整数的公倍数是60，所以每60秒操作序列一定会循环。那么考虑矩阵转移，预处理每秒转移矩阵和60秒的转移矩阵乘积，对\(\lfloor \frac{t}{60} \rfloor\)做60秒的，\(t \bmod 60\)做单秒的。为了新增石头，增加一个节点来提供。

时间复杂度\(O(60^3(\log \lfloor \frac{t}{60} \rfloor+t \bmod 60))\)

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

	rg T data=0,w=1;

	rg char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

		data=data*10+ch-'0',ch=getchar();

	return data*w;

}

template<class T>il T read(rg T&x){

	return x=read<T>();

}

typedef long long ll;

ll f[70],d[70][70],e[70][70][70];

char b[20][20],s[100];

int n,m,t,act,p,a[20][20],c[20][20];

int num(int i,int j){

	return (i-1)*m+j;

}

void mulself(ll a[70][70],ll b[70][70]){

	static ll w[70][70];

	memset(w,0,sizeof w);

	for(int i=1;i<=p;++i)

		for(int k=1;k<=p;++k) if(a[i][k])

			for(int j=1;j<=p;++j)

				w[i][j]+=a[i][k]*b[k][j];

	memcpy(a,w,sizeof w);

}

void mul(ll a[70],ll b[70][70]){

	static ll w[70];

	memset(w,0,sizeof w);

	for(int i=1;i<=p;++i)

		for(int j=1;j<=p;++j)

			w[i]+=a[j]*b[j][i];

	memcpy(a,w,sizeof w);

}

int main(){

//	freopen(".in","r",stdin),freopen(".out","w",stdout);

	read(n),read(m),read(t),read(act);

	for(int i=1;i<=n;++i){

		scanf("%s",s+1);

		for(int j=1;j<=m;++j) a[i][j]=s[j]-'0'+1;

	}

	for(int i=1;i<=act;++i) scanf("%s",b[i]);

	p=n*m+1;

	for(int k=1;k<=60;++k){

		for(int i=1;i<=n;++i)

			for(int j=1;j<=m;++j){

				int x=a[i][j],y=c[i][j];

				if(isdigit(b[x][y])){

					e[k][p][num(i,j)]=b[x][y]-'0';

					e[k][num(i,j)][num(i,j)]=1;

				}

				else if(b[x][y]=='N'&&i>1) e[k][num(i,j)][num(i-1,j)]=1;

				else if(b[x][y]=='W'&&j>1) e[k][num(i,j)][num(i,j-1)]=1;

				else if(b[x][y]=='S'&&i<n) e[k][num(i,j)][num(i+1,j)]=1;

				else if(b[x][y]=='E'&&j<m) e[k][num(i,j)][num(i,j+1)]=1;

				c[i][j]=(y+1)%strlen(b[x]);

			}

		e[k][p][p]=1;

	}

	memcpy(d,e[1],sizeof e[1]);

	for(int k=2;k<=60;++k) mulself(d,e[k]);

	f[p]=1;

	for(int w=t/60;w;w>>=1){

		if(w&1) mul(f,d);

		mulself(d,d);

	}

	for(int w=t%60,i=1;i<=w;++i) mul(f,e[i]);

	ll ans=0;

	for(int i=1;i<p;++i) ans=std::max(ans,f[i]);

	printf("%lld\n",ans);

	return 0;

}