【bzoj2729】[HNOI2012]排队

2015.04.15 13:40 Wed | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

某中学有 n 名男同学,m 名女同学和两名老师要排队参加体检。他们排成一条直线,并且任意两名女同学不能相邻,两名老师也不能相邻,那么一共有多少种排法呢?(注意:任意两个人都是不同的)

Input

只有一行且为用空格隔开的两个非负整数 n 和 m,其含义如上所述。
对于 30%的数据 n≤100,m≤100
对于 100%的数据 n≤2000,m≤2000

Output

输出文件 output.txt 仅包含一个非负整数,表示不同的排法个数。注意答案可能很大。

Sample Input

1 1

Sample Output

12

题解

看起来蛮水的一道题,做起来也的确挺水……
先不考虑老师是否相邻,N+3个人里老师的排列方法有A(n+2,2)种,N+3个空中间插m个女生,并且要记顺序,有A(n+3,m)种,两项相乘。
然后考虑老师相邻,相邻可能存在于n+1个位置,并且此时两人中间不能存在别的人,所以有(n+1)A(n+2,m)种,老师的位置可以调换,所以乘2。
最后所有的男生的排列要算上有A(n,n)
综合起来就是
A(n,n)
(A(n+3,m)A(n+2,2)-2(n+1)*A(n+2,m));
求高精度的时候可以把公式展开,就不用算除法了……
python怎么就wa呢。。。。。。

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Cbig{
    int a[3000];
    int & operator [](const int &b) {
        return a[b];
    }
}ans1,ans2;
void operator *=(Cbig &a,int b)
{
    int p=0;
    for(int i=1;i<=a[0];i++)
        a[i]*=b,a[i]+=p,p=a[i]/10000,a[i]%=10000;
    if(p) a[++a[0]]=p;
}
void operator -=(Cbig &a,Cbig &b)
{
    for(int i=1;i<=a[0];i++)
    if(a[i]-=b[i],a[i]<0) a[i]+=10000,a[i+1]--;
    while(!a[a[0]]) a[0]--;
}
void print(Cbig & a)
{
    printf("%d",a[a[0]]);
    for (int i=a[0]-1;i>=1;i--) printf("%04d",a[i]);
}
int main()
{
    n=read();m=read();
    if (!n||!m||n+2<m-1) {puts("0");return 0;}
    ans1[0]=ans2[0]=ans1[1]=ans2[1]=1;
    for (int i=n+2;i>1;i--) ans1 *= i;
    ans2=ans1,ans2*=2;
    for (int i=n+4-m;i<=n+3;i++) ans1*=i;
    for (int i=n+3-m;i<=n+1;i++) ans2*=i;
    ans1-=ans2;
    print(ans1);
    return 0;
}```