「数论记录」P3330

一只书虫仔 · 2020-06-11 21:44:01 · 题解

P3330 [ZJOI2011]看电影

Description

给定 n 个人和 k 个座位，从 k 个座位等概率的选择出第 l 个座位，对于每个人进行下面的操作：

• 如果 l 座位上没有人就在 l 座位上坐下
• 如果有了就把 l++ 重复操作一
• 如果 l=n 都没坐到座位上就是站票

求全班都坐下的概率。

Solution

典型的古典概型

• 合理方案数把所有座位连成环就可以了，应该是 (k+1)^{n-1}\times(k-n+1)
• 所有方案数这应该很无脑吧 …… k^n

然后就可以得到代码啦 ~

Code 1

#include <bits/stdc++.h>

using namespace std;

long long binpow (long long b, long long p, long long k) {
    b %= k;
    long long res = 1;
    while (p > 0) {
        if (p & 1)
            res = res * b % k;
        b = b * b % k;
        p >>= 1;
    }
    return res;
}

int gcd (int a, int b) {return b == 0 ? a : gcd(b, a % b);}

int main () {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, k;
        scanf("%d%d", &n, &k);
        int ans1 = binpow(k + 1, n - 1, 0x3f3f3f3f) * (k - n + 1);
        int ans2 = binpow(k, n, 0x3f3f3f3f);
        int _gcd = gcd(ans1, ans2);
        ans1 /= _gcd, ans2 /= _gcd;
        printf("%d %d\n", ans1, ans2);
    }
    return 0;
}

期望得分：10 分
Link

加 ll 没用，只有 20 分（

Solution Addition

Why？我们带着数据往里面算

分子：2.1677811057188525650385281027847e+458
分母：1.6069380442589902755419620923412e+460

这两个数都是 450 多位的啊 ……
不用高精不行啊 ……

所以这题需要高精 ……

高精法一：用 C++
就是最后处理 \gcd 的时候会麻烦亿点

高精法二：用 python

这里打一个 python 的 /cy

import fractions
import math

t = int(input())

for i in range(t):
    a, b = map(int, input().split())
    c = ((b + 1) ** (a - 1)) * (b - a + 1)
    d = b ** a
    e = math.gcd(c, d)
    print(c // e, d // e)

但是你发现你只有 90 分，这是为啥呢？

因为我们要特判 n > k 的情况！

import fractions
import math
t = int(input())
for i in range(t):
    a, b = map(int, input().split())
    if a > b:
        print(0, 1)
    else:
        c = ((b + 1) ** (a - 1)) * (b - a + 1)
        d = b ** a
        e = math.gcd(c, d)
        print(c // e, d // e)

然后你就可以 A 了。

AC Link

参考资料：

Z-Y-Y-S 巨佬的 Blog