数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: aimisiyou

[讨论] 排队问题

[复制链接]
 楼主| 发表于 2020-10-28 23:41:16 | 显示全部楼层
不知此题是否等价于球面上有3N个不同的点,按挑选三个点组合构成一个三角形,划分后则N个三角形两两都不相交的方案数为多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-29 23:16:50 | 显示全部楼层
关键词:Hook Formula(钩子公式)
对于LZ提出的问题是该公式在矩形队伍排列的一个特例,具体结果我就不贴了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-10-30 06:52:14 | 显示全部楼层
BeerRabbit 发表于 2020-10-29 23:16
关键词:Hook Formula(钩子公式)
对于LZ提出的问题是该公式在矩形队伍排列的一个特例,具体结果我就不贴 ...

感谢解惑。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
kk.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-1 14:36:39 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-11-1 14:50 编辑

关于编码的描述可以理解,但“从右上角开始填起”,是怎么用编码来表示一个完整的填充过程?或者应是从右下角开始填充?
01.png
02.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-1 15:53:28 | 显示全部楼层
#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;
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-11-4 07:00:29 来自手机 | 显示全部楼层
3*3怎么会只有6种呢?光排好身高最低的四人就有8种。
123
4**
***

124
3**
***

12*
34*
***

12*
3**
4**
再加上对称4种方案
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-11-4 16:57:35 | 显示全部楼层
mathe 发表于 2020-11-4 07:00
3*3怎么会只有6种呢?光排好身高最低的四人就有8种。
123
4**

应该是他算错了吧,3*3是42才对。
hook.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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).
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-1-20 15:01 , Processed in 0.067188 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表