Description

到了难得的假期, 小白班上组织大家去看电影. 但由于假期里看电影的人太多, 很难做到让全班看上同一场电影, 最后大家在一个偏僻的小胡同里找到了一家电影院. 但这家电影院 分配座位的方式很特殊, 具体方式如下:

  1. 电影院的座位共有 \(k\) 个, 并被标号为 \(1 \ldots k\), 每个人买完票后会被随机指定一个座位, 具体来说是从 \(1 \ldots k\) 中等可能的随机选取一个正整数, 设其为 \(L\).
  2. 如果编号 \(L\) 的座位是空位, 则这个座位就分配给此人, 否则将 \(L\) 加一, 继续前面 的步骤.
  3. 如果在第二步中不存在编号 \(L\) 的座位, 则该人只能站着看电影, 即所谓的站票.

小白班上共有 \(n\) 人 (包括小白自己), 作为数学爱好者, 小白想知道全班都能够有座位的 概率是多少.

Input

输入文件第一行有且只有一个正整数 \(T\), 表示测试数据的组数. 第 \(2 - T+1\) 行, 每行 两个正整数 \(n, k\), 用单个空格隔开, 其含义同题目描述.

Output

输出文件共包含 \(T\) 行. 第 \(i\) 行应包含两个用空格隔开的整数 \(A, B\), 表示输入文件中的第 \(i\) 组数据的答案为 \(\frac{A}{B} (gcd(A, B) = 1)\).

Sample Input

3
1 1
2 1
2 2

Sample Output

1 1
0 1
3 4

Data Range

对于 100% 的数据, 满足:\(T \leq 50, n, k \leq 200\)

Explanation

题解已经写的很清楚了, 其实最开始这道题是 @Burst_Zero 告诉我的神题. 然而我这样想了, 然后用 Python 交了一发, 发现无限 WA, 就怀疑是不是自己写错了. 于是从 ZJOI 的官方数据里拿出数据测了一发, 发现所有点都是 AC, 故而开始怀疑 BZOJ 的 Bug 到底有多少~ 最后用了个高精度库交了一发, A 了 (QwQ)

下面是应该正确但是 BZOJ 不给过的 Python 代码:


primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
    67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
    149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
s_primes = set(primes)

def factor(a):
    res = {}
    for i in primes:
        if i > a:
            break
        cnt = 0
        while a % i == 0:
            cnt += 1
            a //= i
        if cnt > 0:
            res[i] = cnt
    return res

def mult_factor(a, mul):
    res = {}
    for i in a:
        res[i] = a[i] * mul
    return res

def add_factor(a, b):
    res = {}
    for i in a:
        res[i] = a[i]
    for i in b:
        if i not in res:
            res[i] = 0
        res[i] += b[i]
    return res

def join_factor(a):
    res = 1
    for i in a:
        res *= i**a[i]
    return res

T = int(input())

for idx in range(0, T):
    n, K = map(int, input().split(' '))
    if n > K:
        print(0, 1)
        continue
    elif n == 1:
        print(1, 1)
        continue
    upper = add_factor(factor(K-n+1), mult_factor(factor(K+1), n-1))
    lower = mult_factor(factor(K), n)
    for i in lower:
        a = lower[i]
        if i in upper:
            b = upper[i]
            c = min(a, b)
            lower[i] -= c
            upper[i] -= c
        pass
    u = join_factor(upper)
    l = join_factor(lower)
    print(u, l)

题解原文链接:http://blog.lightning34.cn/?p=166

概率就是可行方案除以所有方案.

所有方案就是 \(k^n\).

考虑可行方案, 如果加上一个座位使得所有的位置连成环的话, 方案数就是 \((k+1)^n\), 另外由于是环, 有重复的情况, 所以要除以 \(k+1\).

然后再断开, 只要是空位的都可以断开, 所以断开的方案数为 \(k-n+1\).

所以最后的可行方案数为 \((k−n+1) \cdot (k+1)^{n−1}\).

答案可以质因数分解之后高精度求.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 47;

////////////////////////////////////////////////////////////////////////////////
// Thanks to the BigNum implementation by @PegasusWang on:
// http://www.cnblogs.com/PegasusWang/archive/2013/03/23/2977610.html
////////////////////////////////////////////////////////////////////////////////

#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4

class BigNum
{
private:
    int a[50000];    //可以控制大数的位数
    int len;       //大数长度
public:
    BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //构造函数
    BigNum(const int);       //将一个int类型的变量转化为大数
    BigNum(const char*);     //将一个字符串类型的变量转化为大数
    BigNum(const BigNum &);  //拷贝构造函数
    BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算

    friend istream& operator>>(istream&,  BigNum&);   //重载输入运算符
    friend ostream& operator<<(ostream&,  BigNum&);   //重载输出运算符

    BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算
    BigNum operator-(const BigNum &) const;   //重载减法运算符，两个大数之间的相减运算
    BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算
    BigNum operator/(const int   &) const;    //重载除法运算符，大数对一个整数进行相除运算

    BigNum operator^(const int  &) const;    //大数的n次方运算
    int    operator%(const int  &) const;    //大数对一个int类型的变量进行取模运算
    bool   operator>(const BigNum & T)const;   //大数和另一个大数的大小比较
    bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较

    void print();       //输出大数
};
BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
{
    int c,d = b;
    len = 0;
    memset(a,0,sizeof(a));
    while(d > MAXN)
    {
        c = d - (d / (MAXN + 1)) * (MAXN + 1);
        d = d / (MAXN + 1);
        a[len++] = c;
    }
    a[len++] = d;
}
BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
{
    int t,k,index,l,i;
    memset(a,0,sizeof(a));
    l=strlen(s);
    len=l/DLEN;
    if(l%DLEN)
        len++;
    index=0;
    for(i=l-1;i>=0;i-=DLEN)
    {
        t=0;
        k=i-DLEN+1;
        if(k<0)
            k=0;
        for(int j=k;j<=i;j++)
            t=t*10+s[j]-'0';
        a[index++]=t;
    }
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
{
    int i;
    memset(a,0,sizeof(a));
    for(i = 0 ; i < len ; i++)
        a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算
{
    int i;
    len = n.len;
    memset(a,0,sizeof(a));
    for(i = 0 ; i < len ; i++)
        a[i] = n.a[i];
    return *this;
}
istream& operator>>(istream & in,  BigNum & b)   //重载输入运算符
{
    char ch[MAXSIZE*4];
    int i = -1;
    in>>ch;
    int l=strlen(ch);
    int count=0,sum=0;
    for(i=l-1;i>=0;)
    {
        sum = 0;
        int t=1;
        for(int j=0;j<4&&i>=0;j++,i--,t*=10)
        {
            sum+=(ch[i]-'0')*t;
        }
        b.a[count]=sum;
        count++;
    }
    b.len =count++;
    return in;

}
ostream& operator<<(ostream& out,  BigNum& b)   //重载输出运算符
{
    int i;
    cout << b.a[b.len - 1];
    for(i = b.len - 2 ; i >= 0 ; i--)
    {
        cout.width(DLEN);
        cout.fill('0');
        cout << b.a[i];
    }
    return out;
}

BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
{
    BigNum t(*this);
    int i,big;      //位数
    big = T.len > len ? T.len : len;
    for(i = 0 ; i < big ; i++)
    {
        t.a[i] +=T.a[i];
        if(t.a[i] > MAXN)
        {
            t.a[i + 1]++;
            t.a[i] -=MAXN+1;
        }
    }
    if(t.a[big] != 0)
        t.len = big + 1;
    else
        t.len = big;
    return t;
}
BigNum BigNum::operator-(const BigNum & T) const   //两个大数之间的相减运算
{
    int i,j,big;
    bool flag;
    BigNum t1,t2;
    if(*this>T)
    {
        t1=*this;
        t2=T;
        flag=0;
    }
    else
    {
        t1=T;
        t2=*this;
        flag=1;
    }
    big=t1.len;
    for(i = 0 ; i < big ; i++)
    {
        if(t1.a[i] < t2.a[i])
        {
            j = i + 1;
            while(t1.a[j] == 0)
                j++;
            t1.a[j--]--;
            while(j > i)
                t1.a[j--] += MAXN;
            t1.a[i] += MAXN + 1 - t2.a[i];
        }
        else
            t1.a[i] -= t2.a[i];
    }
    t1.len = big;
    while(t1.a[len - 1] == 0 && t1.len > 1)
    {
        t1.len--;
        big--;
    }
    if(flag)
        t1.a[big-1]=0-t1.a[big-1];
    return t1;
}

BigNum BigNum::operator*(const BigNum & T) const   //两个大数之间的相乘运算
{
    BigNum ret;
    int i,j,up;
    int temp,temp1;
    for(i = 0 ; i < len ; i++)
    {
        up = 0;
        for(j = 0 ; j < T.len ; j++)
        {
            temp = a[i] * T.a[j] + ret.a[i + j] + up;
            if(temp > MAXN)
            {
                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
                up = temp / (MAXN + 1);
                ret.a[i + j] = temp1;
            }
            else
            {
                up = 0;
                ret.a[i + j] = temp;
            }
        }
        if(up != 0)
            ret.a[i + j] = up;
    }
    ret.len = i + j;
    while(ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--;
    return ret;
}
BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算
{
    BigNum ret;
    int i,down = 0;
    for(i = len - 1 ; i >= 0 ; i--)
    {
        ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
        down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
    }
    ret.len = len;
    while(ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--;
    return ret;
}
int BigNum::operator %(const int & b) const    //大数对一个int类型的变量进行取模运算
{
    int i,d=0;
    for (i = len-1; i>=0; i--)
    {
        d = ((d * (MAXN+1))% b + a[i])% b;
    }
    return d;
}
BigNum BigNum::operator^(const int & n) const    //大数的n次方运算
{
    BigNum t,ret(1);
    int i;
    if(n<0)
        exit(-1);
    if(n==0)
        return 1;
    if(n==1)
        return *this;
    int m=n;
    while(m>1)
    {
        t=*this;
        for( i=1;i<<1<=m;i<<=1)
        {
            t=t*t;
        }
        m-=i;
        ret=ret*t;
        if(m==1)
            ret=ret*(*this);
    }
    return ret;
}
bool BigNum::operator>(const BigNum & T) const   //大数和另一个大数的大小比较
{
    int ln;
    if(len > T.len)
        return true;
    else if(len == T.len)
    {
        ln = len - 1;
        while(a[ln] == T.a[ln] && ln >= 0)
            ln--;
        if(ln >= 0 && a[ln] > T.a[ln])
            return true;
        else
            return false;
    }
    else
        return false;
}
bool BigNum::operator >(const int & t) const
{
    BigNum b(t);
    return *this>b;
}

void BigNum::print()
{
    int i;
    cout << a[len - 1];
    for(i = len - 2 ; i >= 0 ; i--)
    {
        cout.width(DLEN);
        cout.fill('0');
        cout << a[i];
    }
    // cout << endl;
}

////////////////////////////////////////////////////////////////////////////////
// End of BigNum library
////////////////////////////////////////////////////////////////////////////////

int primes[47] = { 46,
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
    157, 163, 167, 173, 179, 181, 191, 193, 197, 199 };

class factor
{
public:
    lli cnt[maxn];
    factor(lli in) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= primes[0]; i++) {
            if (primes[i] > in) break;
            while (in % primes[i] == 0)
                in /= primes[i], cnt[i] += 1;
        } return ; }
};
factor operator * (factor a, factor b)
{
    factor c(1);
    for (int i = 1; i <= primes[0]; i++)
        c.cnt[i] = a.cnt[i] + b.cnt[i];
    return c;
}
factor operator ^ (factor a, lli powr)
{
    factor b(1);
    for (int i = 1; i <= primes[0]; i++)
        b.cnt[i] = a.cnt[i] * powr;
    return b;
}
ostream& operator << (ostream& out, factor f)
{
    bool printed = false;
    for (int i = 1; i <= primes[0]; i++) {
        if (f.cnt[i] <= 0) continue;
        if (printed) out << "*";
        printed = true;
        out << primes[i] << "^" << f.cnt[i];
    }
    if (!printed) out << "1";
    return out;
}

int T;
lli n, k;

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%lld%lld", &n, &k);
        if (n > k) {
            printf("0 1\n");
            continue;
        }
        factor upper = factor(k-n+1) * (factor(k+1) ^ (n-1));
        factor lower = factor(k) ^ n;
        for (int i = 1; i <= primes[0]; i++) {
            int a = upper.cnt[i], b = lower.cnt[i];
            upper.cnt[i] -= min(a, b);
            lower.cnt[i] -= min(a, b);
        }
        BigNum u = 1, l = 1;
        for (int i = 1; i <= primes[0]; i++) {
            for (int j = 1; j <= upper.cnt[i]; j++)
                u = u * primes[i];
            for (int j = 1; j <= lower.cnt[i]; j++)
                l = l * primes[i];
        }
        u.print();
        cout << ' ';
        l.print();
        cout << '\n';
    }
    return 0;
}