526互联

ARC166 C LU/RD Marking

发布时间 2023-11-26 00:10:37作者: Martian148

Link

ARC166 C LU RD Marking

Question

给一个 \(n\) 行 \(m\) 列的网格，它的所有网格线上共有 \(n(m+1)\) 条竖边，有 \((n+1)m\) 条横边

有如下两中操作

  • 选一个上面和左边的网格线没有被涂黑的格子，并涂黑着两条线
  • 选一个下面和右边的网格线都没被涂黑的各自，并涂黑着两条线

这两种操作可以执行任意次，求可能得到不同的黑边的数量，答案对 \(998244353\) 取模

image.png

Solution

我们考虑一次操作只会对左上和右下的折线产生影响，所以考虑把吐斜着劈开

image.png

然后考虑每个折线，动态规划，定义 \(DP[i]\) 表示折线长度为 \(i\) 的时候的方案数

转移方程为，如果不取 \([n-1,n]\) 这条线段，那么方案数就是 \(DP[i-1]\) 如果取了 \(DP[n-1,n]\) 那么方案书就是 \(DP[i-2]\)，所以

\[DP[i]=DP[i-1]+DP[i-2] \]

发现这是一个斐波那契数列

答案就是把所有的 \(DP[i]\) 乘起来，我们强制要求\(H<W\) 答案就是

\[{DP[2H+1]}^{W-H} \times (\prod \limits_{i=1}^{H} 2i)^2 \]

对于前面一部分，使用快速幂

对于后面一部分，预处理就好了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+5;
const LL TT = 998244353;
int T;
LL Fac[maxn],H,W,F[maxn],ans;
inline int read(){
    int ret = 0, f = 1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f = -f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-48,ch=getchar();
    return ret;
}
LL qpow(LL a,LL b){
    LL ret=1;
    while(b){
        if(b&1) ret=ret*a%TT;
        a=a*a%TT;
        b>>=1;
    }
    return ret;
}
int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    T=read();

    Fac[1]=1;Fac[2]=2;
    for(int i=3;i<maxn;i++)
        Fac[i]=(Fac[i-1]+Fac[i-2])%TT;
    F[0]=1;
    for(int i=2;i<maxn;i+=2)
        F[i]=(F[i-2]*Fac[i])%TT;
    while(T--){
        H=read();W=read();
        if(H>W) swap(H,W);
        ans = qpow(Fac[H*2+1],W-H)*F[H*2]%TT*F[H*2]%TT;
        printf("%lld\n",ans);
    }
    return 0;
}

Summary