• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

矩阵 题解

开发技术 开发技术 6小时前 3次浏览

矩阵 题解

成功被低年级吊打

本文版权归Azazel与博客园共有,欢迎转载,但需保留此声明,并给出原文地址,谢谢合作。

原文地址:https://www.cnblogs.com/Azazel/p/15031854.html

题意

(~~~~)

题解

(~~~~) A001499,写完了。

(~~~~) 考虑转化题意,改为:令 (f_i) 表示对长为 (n) 的,初始全部为 (0) 的数列进行操作,每次选择两个位置 (+1) ,求进行 (n) 次操作,使得所有数都为 (2) 的操作方案数。

(~~~~) 那么我们考虑 (texttt{DP}),设 (dp_i) 表示填一个长为 (n) 的数列,使其满足条件的方案数。则有边界 (dp_0=1,dp_2=1) 。同时设一个辅助数组 (f_i) 表示一个长为 (n) ,其中填了两个 (1) 的使其满足条件的方案数。

(~~~~) 考虑如何推 (dp) 数组,假设现在在推 (dp_i),此时我们需要缩小至少 (1) 的规模,也就是对一个格子操作两次。因此分为以下两种情况:

  • 两次选择的另一个格子相同,则此后状态为 (dp_{i-2}),选择另一个格子的方案数为 (C_{i-1}^1) ,同时该操作只需选择任意两次行操作即可,不用考虑顺序。综上该部分为 (dp_{i-2}times C_{i-1}^1times C_{i}^2)
  • 两次选择的另一个格子不相同,则此后状态为 (f_{i-1}),选择另两个格子的方案数为 (C_{i-2}^2),同时该操作有顺序区分。综上该部分为 (f_{i-1}times C_{i-1}^2times A_{i}^2)

(~~~~) 再来考虑推 (f) 数组,此时必须把这两个 (1) 都消掉,所以分为以下三种情况:

  • 在选择第一个 (1) 时就选到了另一个 (1) ,之后的状态为 (dp_{i-2}),只能选择另一个格子,同时在前 (i-1) 次操作中选择一次进行该操作(有 (1) 次用来填这两个 (2) )。综上该部分为 (dp_{i-2}times 1times C_{i-1}^1)
  • 两个 (1) 选的另一个格子不同,之后的状态为 (f_{i-2}),注意到两次行操作选择格子不同会导致行不同所以应该有 (A_{i-2}^2) 种选格子方式,最后还是两次操作不同故有序。综上该部分为 (f_{i-2}times A_{i-2}^2times A_{i-1}^2)
  • 两个 (1) 选的另一个格子相同,之后的状态为 (dp_{i-3}) ,仍然选择另一个格子方案数为 (C_{i-2}^1) ,最后安排行操作方案为 (A_{i-1}^2) 。综上该部分为 (dp_{i-3}times C_{i-2}^1times A_{i-1}^2)

(~~~~) 最后 (mathcal{O(n)}) (texttt{DP})就行了。

代码

查看代码
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int MOD=998244353;
ll Fac[10000005],Inv[10000005];
ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%MOD;
		b>>=1;a=a*a%MOD;
	}
	return ret;
}
ll C(ll r,ll n){return Fac[n]*Inv[r]%MOD*Inv[n-r]%MOD;}
ll A(ll r,ll n){return Fac[n]*Inv[n-r]%MOD;}
ll dp[10000005],f[10000005];
int main() {
	int n;
	scanf("%d",&n);
	Fac[0]=1;Inv[0]=1;
	for(int i=1;i<=n;i++) Fac[i]=Fac[i-1]*i%MOD;
	Inv[n]=qpow(Fac[n],MOD-2);
	for(int i=n-1;i>=1;i--) Inv[i]=Inv[i+1]*(i+1)%MOD;
	dp[0]=1; dp[2]=1;
	f[2]=1;
	ll Ans=1;
	for(int i=3;i<=n;i++)
	{
		//            状态   选择格子     选择操作 
		dp[i]=(dp[i]+dp[i-2]*C(1,i-1)%MOD*C(2,i)%MOD)%MOD;
		dp[i]=(dp[i]+f[i-1] *C(2,i-1)%MOD*A(2,i)%MOD)%MOD;
		f[i]=(f[i]+  dp[i-2]*1           *C(1,i-1)%MOD)%MOD;
		f[i]=(f[i]+  f[i-2] *A(2,i-2)%MOD*A(2,i-1)%MOD)%MOD;
		f[i]=(f[i]+  dp[i-3]*C(1,i-2)%MOD*A(2,i-1)%MOD)%MOD;
		Ans=(Ans+dp[i])%MOD;
	}
	printf("%lld",Ans);
	return 0;
} 

程序员灯塔
转载请注明原文链接:矩阵 题解
喜欢 (0)