[校内模拟]三格骨牌

骨牌"/>

[校内模拟]三格骨牌

Description

T次询问，每次将一个nm的棋盘分成nm/3块大小为3的四连通块，再给每个四连通块标号，使得每块的标号不同，并且对于一个格子，其左边和上边的标号要小于等于其本身的标号
问方案数，对10^9+7取模
T<=10,n,m<=10^4

Solution

考虑按标号从小到大填连通块，那么每次填完后的图形必然是左上角的一块
考虑这一块的轮廓线，必然只有往上和往右的，那么我们设1为上，0为右，可以用一个2^(n+m)的二进制状态表示轮廓线
考虑转移，不难发现每次都是对轮廓线长度为4的一段进行转移，并且只有4种转移
1000->0001
1010->0011
1100->0101
1110->0111
发现转移可以规约为“选择一个1，和其右边三格的0交换”
这个和中间的数无关，于是我们把状态模3分组，每组的操作次数是一定的，最后用组合数组合起来
考虑一组，问题变成了从11…11000…000转移到00.00111…111，一次转移是相邻的10变为01
重新考虑原来的轮廓线意义，发现和原问题基本等价，只是每次选择一个大小为1的块转移，这样的方案数等价于直接标号的方案数
问题变成了nm的网格图，将1~nm!填入，满足对于一个格子，其左边和上边格子填的数要严格小于其上的数
这相当于问对于有多少个nm的标准杨表，运用Frame-Robinson-Thrall可以直接得出答案
复杂度O(nm+T(n+m)log)

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;typedef long long ll;const int Mo=1e9+7;int pwr(int x,int y) {int z=1;for(;y;y>>=1,x=(ll)x*x%Mo)if (y&1) z=(ll)z*x%Mo;return z;
}int n,m,ty,fac[33333334],inv[20000],cnt[3][2];int calc(int n,int m) {int ans=1;fo(i,1,n+m-1) {int l=max(1,i-m+1),r=min(n,i);ans=(ll)ans*pwr(inv[i],r-l+1)%Mo;}return ans;
}int main() {freopen("trominoes.in","r",stdin);freopen("trominoes.out","w",stdout);fac[0]=1;fo(i,1,33333333) fac[i]=(ll)fac[i-1]*i%Mo;inv[0]=inv[1]=1;fo(i,2,19999) inv[i]=(ll)(Mo-Mo/i)*inv[Mo%i]%Mo;for(scanf("%d",&ty);ty;ty--) {scanf("%d%d",&n,&m);fo(i,0,2) fo(j,0,1) cnt[i][j]=0;fo(i,1,n+m) cnt[i%3][i<=n]++;int c=0;fo(i,0,2) c+=cnt[i][0]*cnt[i][1];int ans=fac[c];fo(i,0,2) ans=(ll)ans*calc(cnt[i][0],cnt[i][1])%Mo;printf("%d\n",ans);}return 0;
}