当前位置 : 主页 > 手机开发 > ROM >

[集训]Trominoes,钩子公式运用

来源:互联网 收集:自由互联 发布时间:2021-06-10
题意 用 这四种骨牌密铺n*m的正方形矩阵,可以不选,求方案数。n*m=1E8。多组询问。 思考 用如上的表达难以进行计算,尝试转化为一种新的组合解释。 若从右上角开始填起,我们强制

题意

分享图片这四种骨牌密铺n*m的正方形矩阵,可以不选,求方案数。n*m<=1E8。多组询问。


 

思考

用如上的表达难以进行计算,尝试转化为一种新的组合解释。

若从右上角开始填起,我们强制要求里面的轮廓线是单调增的。例如:

分享图片这种方法既不影响合法性,又不会重复计数。

可以看见,我们只关心轮廓线的形状,不关心其他部分的细节,因此我们可以用长度为n+m的01串来表示其反向。在此处,默认01串从左下角向右上角写起,0代表上,1代表右。

每填充一个骨牌,可以发现这样的转移:

0001->1000

0011->1010

0101->1100

0111->1110

除了第四位上的数字,其余的三位在二进制表示下是完备的,也就是说,可以看做是单一的1先前移动了3位。

至此,原问题表述为:给定一个开头有n个1,末尾有m个0的字符串,每次可将1向前移动三位到一个字符为0的位置上,问构成开头有m个0,末尾有n个1的字符串的方案数有多少个。

该问题又可以划分为三个子问题,因为位置模3的余数不同的互不影响。也就是考虑若每次向右移动一个,有多少方案。

这个问题可以看做是经典的买票问题,使用钩子公式解决。复杂度O(n*m/3+T*n)


 

代码

分享图片
 1 #include<bits/stdc++.h>
 2 #define mod 1000000007
 3 using namespace std;
 4 typedef long long int ll;
 5 ll fac[33333335],n,m,T;
 6 void init()
 7 {
 8     fac[0]=1;
 9     for(int i=1;i<=33333333;++i)
10         fac[i]=fac[i-1]*i%mod;
11 }
12 ll qpow(ll x,ll y)
13 {
14     ll ans=1,base=x;
15     while(y)
16     {
17         if(y&1)
18             ans=ans*base%mod;
19         base=base*base%mod;
20         y>>=1;
21     }
22     return ans;
23 }
24 inline ll C(int x,int y)
25 {
26     return fac[x]*qpow(fac[y],mod-2)%mod*qpow(fac[x-y],mod-2)%mod;
27 }
28 inline ll get(ll n,ll m)
29 {
30     ll ans=1,sum=1;
31     for(int i=1;i<=n;++i)
32     {
33         ans=ans*fac[i+m-1]%mod;
34         sum=sum*fac[i-1]%mod;
35 //        for(int j=1;j<=m;++j)
36 //            ans=ans*(i+j-1)%mod;
37     }
38     return fac[n*m]*qpow(ans,mod-2)%mod*sum%mod;
39 }
40 int main()
41 {
42     ios::sync_with_stdio(false);
43     init();
44     cin>>T;
45     while(T--)
46     {
47         cin>>n>>m;
48         if(n*m%3!=0)
49         {
50             cout<<0<<endl;
51             continue;
52         }
53         if(n%3!=0)
54             swap(n,m);
55         int base0=m/3;
56         int left0=base0,left1=base0+(m%3>0),left2=base0+(m%3>1);
57         ll ans=get(n/3,left0)*get(n/3,left1)%mod*get(n/3,left2)%mod;
58         ans=ans*C((left0+left1+left2)*n/3,left0*n/3)%mod;
59         ans=ans*C((left1+left2)*n/3,left1*n/3)%mod;
60         cout<<ans<<endl;
61     }
62     return 0;
63 }
View Code
上一篇:一键部署安装
下一篇:temp for @青
网友评论