Description
有m个在[0,2^n)内均匀随机取值的变量，求至少有两个变量取值相同的概率。
为了避免精度误差，假设你的答案可以表示成号的形式(其中(a,b)= 1)，你需要
输出a和b对108+3取模后的值。
Input
从文件 random.in 中读入数据。
第一行两个正整数 n,m。
Output
输出到文件 random.out 中。
一行两个整数，它们的含义如题所述。
Sample Input
【样例 1 输入】
3 2
【样例 1 输出】
1 8
Sample Output
【样例 2 输入】
1 3
【样例 2 输出】
1 1
Hint
【样例 3 输入】
4 3
【样例 3 输出】
23 128
【子任务】
对于 10% 的数据，nm < 16；
对于 30% 的数据，nm < 64；
对于 50% 的数据，nm ≤ 10^3 ；
对于 70% 的数据，m ≤ 10 6 ；
对于 100% 的数据，1 ≤ n ≤ 10^18 ,2 ≤ m ≤ 10^18 。
思路
- 不会逆元，不会数学，式子书写太烂，几行代码改到吐了。。。
- qpow：快速幂； jie(m)：m!中因子2的个数； jiez(a，k)：从a开始连续k个数的乘积 % mod
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1e6+3;
long long n,m;
long long qpow(long long x,long long a)
{
long long ans=1;
while(a)
{
if(a&1) ans=ans*x%mod;
x=x*x%mod;
a>>=1;
}
return ans;
}
long long jiez(long long a,long long k)
{
if(k>=mod) return 0;
long long ans=1;
for(int i=a;i<a+k;++i) ans=ans*i%mod;
return ans;
}
long long jie(long long a)
{
long long ans=0;
while(a) a/=2,ans+=a;
return ans;
}
int main()
{
//freopen("5103.in","r",stdin);
//freopen("5103.out","w",stdout);
scanf("%lld%lld",&n,&m);
long long num2=jie(m-1),ni=qpow(qpow(2,num2),mod-2);
long long fenm=(qpow(qpow(2,n),m-1)*ni%mod);
long long fenz=(jiez((qpow(2,n)-m%mod+1+mod)%mod,m-1)*ni)%mod;
cout<<(fenm-fenz+mod)%mod<<' '<<fenm<<'
';
return 0;
}