Solvution

题意是一年有天,然后总共有个人,求这个人中,至少有两个人生日相同的概率。
直接求答案似乎不能做,考虑我们可以求什么。
我们可以算出总情况数,还有所有人均不相同的情况数,不难发现所求的答案即为
把右边这一项提出来,就有
我们发现分母中只有质因数,然后我们又有的次数是等于的次数,于是约分问题就可以转化求为的次数。实际上的幂次是
对于分数取模步骤如下由费马小定理可得所以

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int kcz = 1e6 + 3;
inline LL fast_mul(LL x , LL y)
{
    LL ans = 0 , res = x;
    while(y)
    {
        if(y & 1) ans = (ans + res) % kcz;
        res = (res << 1) % kcz;
        y >>= 1;
    }
    return ans;
}
inline LL fast_pow(LL x , LL y)
{
    LL ans = 1 , res = x;
    while(y)
    {
        if(y & 1) ans = fast_mul(ans , res);
        res = fast_mul(res , res);
        y >>= 1;
    }
    return ans;
}
inline LL get_pow(LL x)
{
    LL res = 0 , temp = 2;
    while(x >= temp)
    {
        res = res + x / temp;
        temp <<= 1;
    }
    return res;
}
inline LL get_num(LL n , LL k)
{
    if(k >= kcz) return 0;
    LL res = 1;
    while(k && n)
    {
        res = fast_mul(res , n);
        k-- , n--;
    }
    return res;
}
LL n , k;
LL sum , val, p , cnt, mother;
int main()
{
    cin >> n >> k;
    if(log2(k) > n) cout << "1 1\n";
    else
    {
        cnt = fast_pow(2 , get_pow(k - 1)); // 2 in (k - 1)!
        mother = fast_pow(cnt , kcz - 2); // 2^mother in (k - 1)!
        p = (fast_pow(2 , n) - 1 + kcz) % kcz; // mul_begin
        val = fast_mul(get_num(p , k - 1) , mother); // son
        sum = fast_mul(fast_pow(fast_pow(2 , k - 1) , n) , mother); // all_sum
        val = (sum - val + kcz) % kcz;
        cout << val << ' ' << sum << endl;
    }
    return 0;
}

Quote

Codeforces 711E ZS and The Birthday Paradox
Legendre's formula

发表评论

电子邮件地址不会被公开。 必填项已用*标注