[Training] TROMinoES, hooks

By Rom

Title

Use share pictureThese four domino secrets Shop n*m square matrix, you can choose not to choose, find the number of schemes. n*m<=1E8. Multiple groups of inquiries.

Thinking

It is difficult to calculate with the above expression, try to transform it into a new combination interpretation.

If starting from the upper right corner, we force the contour line inside to increase monotonically. For example:

share pictureThis method neither affects legality nor does it Repeat counting.

It can be seen that we only care about the shape of the contour line and do not care about the details of other parts, so we can use the 01 string with a length of n+m to represent the reverse. Here, the default 01 string is written from the lower left corner to the upper right corner, 0 stands for up, and 1 stands for right.

Every time a domino is filled, such a transfer can be found:

0001->1000

< p>0011->1010

0101->1100< /p>

0111->1110

Except for the number on the fourth digit, the remaining three digits are in binary representation Complete, that is to say, can be regarded as a single 1 moved 3 places previously.

So far, the original question is stated as: Given a string with n 1s at the beginning and m 0s at the end, each time 1 can be moved forward by three digits to the position where a character is 0. , Ask how many schemes are there to form a string with m 0s at the beginning and n 1s at the end.

The problem can be divided into three sub-problems, because the remainder of the position modulo 3 does not affect each other. That is, consider how many options there are if one moves to the right at a time.

This problem can be regarded as a classic ticket purchase problem, which is solved by the hook formula. Complexity O(n*m/3+T*n)

Code

share picture 

 1 #include

 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[xy],mod-2< /span>)%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 span>]%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<endl;

61 }

62 return 0;

63 }

View Code

share picture 

 1 #include

 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[xy],mod-2< /span>)%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 span>]%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<endl;

61 }

62 return 0;

63 }

View Code

 1 #include

 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[xy],mod-2< /span>)%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 span>]%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<endl;

61 }

62 return 0;

63 }

, , , ,

Leave a Comment

Your email address will not be published.