排队问题

aimisiyou

不知此题是否等价于球面上有３Ｎ个不同的点，按挑选三个点组合构成一个三角形，划分后则Ｎ个三角形两两都不相交的方案数为多少？

BeerRabbit

关键词：Hook Formula（钩子公式）
对于LZ提出的问题是该公式在矩形队伍排列的一个特例，具体结果我就不贴了。

aimisiyou

BeerRabbit 发表于 2020-10-29 23:16
关键词：Hook Formula（钩子公式）
对于LZ提出的问题是该公式在矩形队伍排列的一个特例，具体结果我就不贴 ...

感谢解惑。

aimisiyou

对于一个有效格子A_i,其上面的有效格子数为Up_i,其右边的有效格子数为Right_i
则答案为Ans=n!/((Up_1 + Right_1 +1)*(Up_2 + Right_2 +1)*....*(Up_n + Right_n +1))

即结果为24!/(10*9*8*7*6*5*4*3)/(9*8*7*6*5*4*3*2)/(8*7*6*5*4*3*2*1)=23371634

aimisiyou

关于编码的描述可以理解，但“从右上角开始填起”，是怎么用编码来表示一个完整的填充过程？或者应是从右下角开始填充？

aimisiyou

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int ll;
ll fac[33333335],n,m,T;
void init()
{
    fac[0]=1;
    for(int i=1;i<=33333333;++i)
        fac[i]=fac[i-1]*i%mod;
}
ll qpow(ll x,ll y)
{
    ll ans=1,base=x;
    while(y)
    {
        if(y&1)
            ans=ans*base%mod;
        base=base*base%mod;
        y>>=1;
    }
    return ans;
}
inline ll C(int x,int y)
{
    return fac[x]*qpow(fac[y],mod-2)%mod*qpow(fac[x-y],mod-2)%mod;
}
inline ll get(ll n,ll m)
{
    ll ans=1,sum=1;
    for(int i=1;i<=n;++i)
    {
        ans=ans*fac[i+m-1]%mod;
        sum=sum*fac[i-1]%mod;
//        for(int j=1;j<=m;++j)
//            ans=ans*(i+j-1)%mod;
    }
    return fac[n*m]*qpow(ans,mod-2)%mod*sum%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        if(n*m%3!=0)
        {
            cout<<0<<endl;
            continue;
        }
        if(n%3!=0)
            swap(n,m);
        int base0=m/3;
        int left0=base0,left1=base0+(m%3>0),left2=base0+(m%3>1);
        ll ans=get(n/3,left0)*get(n/3,left1)%mod*get(n/3,left2)%mod;
        ans=ans*C((left0+left1+left2)*n/3,left0*n/3)%mod;
        ans=ans*C((left1+left2)*n/3,left1*n/3)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

aimisiyou

当m=n=3时，程序运行结果为6.
当m=3，n=,4时，程序运行结果为12.
当m=n=6时，程序运行结果为277200。

mathe

3*3怎么会只有6种呢？光排好身高最低的四人就有8种。
123
4**
***

124
3**
***

12*
34*
***

12*
3**
4**
再加上对称4种方案

BeerRabbit

mathe 发表于 2020-11-4 07:00
3*3怎么会只有6种呢？光排好身高最低的四人就有8种。
123
4**

应该是他算错了吧，3*3是42才对。

aimisiyou

mathe 发表于 2020-11-4 07:00
3*3怎么会只有6种呢？光排好身高最低的四人就有8种。
123
4**

3*3对应的不是前面的排队问题（9！/5*4*3*4*3*2*3*2*1=42）,而是骨牌填充问题（3*3）.