Codeforces 1178C. Tiles

考虑一块块填，首先 $(1,1)$ 有 $4$ 种方案

然后根据 $(1,1)$ 的右边颜色，$(1,2)$ 有两种方案，$(1,3)$ 根据 $(1,2)$ 也有两种方案...

考虑 $(2,1)$ 根据 $(1,1)$ 有两种方案，$(3,1)$ 也有两种....

然后发现，如果我们确定了 $(1,1)$ 到 $(1,m)$ ，确定了 $(1,1)$ 到 $(n,1)$ ，那么之后所有位置都可以根据它们的左边颜色和上面颜色确定

那么方案数即为填左边一列和上边一行的方案数

那么答案整理一下就是 $2^{n+m}$

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int mo=;

int n,m;

inline int ksm(int x,int y)

{

    int res=;

    while(y) { if(y&) res=1ll*res*x%mo; x=1ll*x*x%mo; y>>=; }

    return res;

}

int main()

{

    n=read(),m=read();

    printf("%d\n",ksm(,n+m));

    return ;

}

巴特西

Codeforces 1178C. Tiles

最新文章

热门文章