论坛 › 趣题妙解 › 排队问题

aimisiyou 发表于 2020-10-28 23:41:16

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

BeerRabbit 发表于 2020-10-29 23:16:50

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

aimisiyou 发表于 2020-10-30 06:52:14

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

感谢解惑。

aimisiyou 发表于 2020-10-30 06:57:45

本帖最后由 aimisiyou 于 2020-10-30 09:46 编辑

对于一个有效格子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 发表于 2020-11-1 14:36:39

本帖最后由 aimisiyou 于 2020-11-1 14:50 编辑

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

aimisiyou 发表于 2020-11-1 15:53:28

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int ll;
ll fac,n,m,T;
void init()
{
    fac=1;
    for(int i=1;i<=33333333;++i)
      fac=fac*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*qpow(fac,mod-2)%mod*qpow(fac,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%mod;
      sum=sum*fac%mod;
//      for(int j=1;j<=m;++j)
//            ans=ans*(i+j-1)%mod;
    }
    return fac*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 发表于 2020-11-1 15:58:39

本帖最后由 aimisiyou 于 2020-11-1 16:02 编辑

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

mathe 发表于 2020-11-4 07:00:29

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

124
3**
***

12*
34*
***

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

BeerRabbit 发表于 2020-11-4 16:57:35

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


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

aimisiyou 发表于 2020-11-6 11:03:28

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）.

查看完整版本: 排队问题