题意
求一年有 $2^n$ 天，$m$ 个人出现两人生日相同的概率。答案输出对 $10^6+3$ 的取模分子和分母（约分后）。
思路
首先想不进行优化的数学计算方法，求出两人生日相同的概率不容易，但我们可以求出所有人生日不同的概率（也就是排列数除以所有情况数），再用 $1$ 减掉，即得公式
$$
p=1-\frac{A_{2^n}^{m}}{2^{nm}}
$$
展开 $A^m_{2^n}$ 得到
$$
p=1-\frac{\left(2^{n}\right)\left(2^{n}-1\right)\left(2^{n}-2\right)\cdots\left(2^{n}-m+1\right)}{2^{nm}}
$$然后可以很容易想到用快速幂进行进行计算，求得分子和分母。
但是，题目要求约分。容易看出，分数线上下同除的数一定是 $2^k$（因为分母是$2^{nm}$），且分子一定有剩余（不然答案就是 $0$ 了），因此只要知道分子中可以分解出几个 $2$ 就可以了。
于是，可以使用勒让德定理（但我不会证明）。
$$
{v_p\left(n!\right)=\underset{i=1}{\overset{\infty}{\sum}}\lfloor\frac{n}{p^{i}}\rfloor}
$$
（$v_p(x)$ 表示 $x$ 质因数分解后 $p$ 的指数）这样，分子中可以分解出几个 $2$ 就可以用勒让德定理求出。
下面讲一下具体的方法：
首先想到的是用 $v_2(2^n!)-v_2((2^n-m)!)$ 算出结果，但 $1\le n \le 10^{18}$，显然TLE。
然后想到分类讨论分子的各个组成部分，首先， $2^n$ 中一定有 $n$ 个 $2$，然后考虑之后每一项，可知每一项中 $2$ 的个数取决于减去的数中 $2$ 的个数，即而所有除 $2^n$ 之外的项中 $2$ 的个数就是每次减去的数中 $2$ 的个数的和，也就是它们乘积中 $2$ 的个数，即
$$
num=n+v_2(1 \times 2 \times 3 \times \cdots \times m-1))=n+v_2((m-1)!)
$$
此时可以计算。
所以，约分除去的数就是
$$
2^{n+v_2((m-1)!)}
$$
可用快速幂求出。最后一步，分子和分母同时乘需要除去的数的乘法逆元，答案就出来了。
注意
- 注意数据规模，要开
long long，计算 $nm$ 时需要__int128。 - 可以
#define int __int128这时主函数类型要改，且注意输出时要强制转换为long long（cout<<(long long)(......)<<......），或者写输出函数（因为标准输入输出不支持__int128），也要注意选择合适的编译器版本。 - 注意当 $2^n\le m$ 时直接输出
1 1退出。 - 注意计算 $2^i$ 时写成
1LL<<i，不写LL会炸。
- 注意数据规模，要开
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
const int mod=1e6+3;
int n，m;
bool check(){
int x=1;
for(int i=1;i<=n;i++){
x=x*2ll;
if(x>=m)
return false;
}
return true;
}
int qpow(int _n，int _k){
int ans=1ll;
while(_k) {
if(_k&1ll)
ans=ans*_n%mod;
_n=_n*_n%mod;
_k>>=1ll;
}
return ans;
}
int jian(int _a，int _b){
return (_a%mod-_b%mod+mod)%mod;
}
int getk(int _n){
int sum=0;
for(int i=1;_n/(1ll<<i)>0;i++){
sum+=_n/(1ll<<i);
}
return sum;
}
main(){
ll t_n，t_m;
cin>>t_n>>t_m;
n=t_n;m=t_m;
if(check()){
cout<<1<<" "<<1<<endl;
return 0;
}
int a=1;
for(int i=1;i<=m;i++){
a=a*jian(qpow(2，n)，i-1)%mod;
if(a==0)break;
}
int b=qpow(2，n*m);
int k1=n;
int k2=getk(m-1);
int k=k1+k2;
int inv_k=qpow(k，mod-2);
cout<<(ll)((b*qpow(500002，k)%mod-a*qpow(500002，k)%mod+mod)%mod)<<" "<<(ll)(b*qpow(500002，k)%mod)<<endl;
return 0;
}