【NOI2019模拟2019.7.1】三格骨牌（轮廓线dp转杨图上钩子定理）

Description

\(n,m<=1e4,mod ~1e9+7\)

题解：

显然右边那个图形只有旋转90°和270°后才能放置。

先考虑一个暴力的轮廓线dp：

假设已经放了编号前i的骨牌，那么这些骨牌形成的图形一定是杨表那样的。

对轮廓线来考虑，不妨设1表示向上走，0表示向右走。

初始状态是：111…(n个1)000..(m个0)

那么四种转移为：

1. 1110->0111
2. 1000->0001
3. 1010->0011
4. 1100->0101

这样暴力dp应该能过n,m<=10的。

观察这四种转移，中间的两位都不变，只是把第1位的1移到第4位。

那么按\(mod~3\)分开做，问题变为有一个x+y长的01序列，一开始是x个1+y个0.

每次可以把一个1和紧接的0交换，求最后变为x个0+y个1的方案数。

再把这个转到x×y的杨图上去，一开始轮廓线紧贴左边界和上边界，每次可以把轮廓线的一行改宽一列，且还要满足轮廓线的性质，其实这就是x×y的杨图个数，套钩子定理即可。

那么\(Ans=(xy)!/\prod_{i=0}^{n-1}\prod_{j=1}^{m-1}(i+j+1)!\)

Code：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int fac[34000100];
int _,n,m;
int main() {
    freopen("trominoes.in", "r", stdin);
    freopen("trominoes.out", "w", stdout);
    ll s=1;
    fac[0]=1;
    rep(i,1,34000000) fac[i]=(ll)fac[i-1]*i%mod;
    for (scanf("%d",&_);_;_--) {
        scanf("%d%d",&n,&m);
        if (n*m%3!=0) {
            puts("0");
            continue;
        }
        if (n%3!=0) swap(n,m);
        ll ret=fac[n*m/3],rg=1;
        rep(i,0,m) {
            ret=ret*fac[i/3]%mod;
            rg=rg*fac[i/3+n/3]%mod;
        }
        ret=ret*powmod(rg,mod-2)%mod;
        printf("%lld\n",ret);
    }
}

【NOI2019模拟2019.7.1】三格骨牌（轮廓线dp转杨图上钩子定理）

原文：https://www.cnblogs.com/coldchair/p/11116902.html