http://codeforces.com/problemset/problem/711/E 这个题目的关键在于，取余的数字只有\(10^6+3\) 然后这个概率其实非常简单，就是\[1-\frac{\prod_{i=0}^{k-1}(2^n-i)}{\prod_{i=0}^{k-1}2^n}\] 我们只需要求\[\frac{\prod_{i=0}^{k-1}(2^n-i)}{\prod_{i=0}^{k-1}2^n}\]的最简分数就可以了。 因为\(\prod_{i=0}^{k-1}2^n\)中的因子只有\(2\)，所以我们需要知道\(\prod_{i=0}^{k-1}(2^n-i)\)中有多少个因子\(2\)可以约去。 实际上，我们只需要知道\(1\)到\(k-1\)之间有几个因子\(2\)即可，这个计算很简单。然后求出逆元乘到结果中即可。 然后因为分子其实是连续几个相差\(1\)的数字相乘，所以如果数字个数超过\(10^6+3\)，这个分子取余\(10^6+3\)之后一定为\(0\)。 这样这个问题在\(O(mod)\)的时间复杂度下就可以解决。
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
| #include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL mod=1e6+3;
LL n,k;
LL kk(LL t,LL x)
{
if(x==0) return 1;
LL p=kk(t,x/2);
p=p*p;
p%=mod;
if(x%2) p*=t;
p%=mod;
return p;
}
int main()
{
scanf("%I64d%I64d",&n,&k);
if(n<=63)
{
if((1ll<<n)<k)
{
cout<<1<<" "<<1;
return 0;
}
}
LL p=1;
LL x=kk(2,n);
for(int i=1;i<k;i++)
{
x--;
p*=x;
p%=mod;
if(p==0) break;
}
LL w=0;
LL o=k-1;
while(o!=0)
{
o/=2;
w+=o;
}
LL inv=kk(kk(2,mod-2),w);
LL q=kk(2,n);
q=kk(q,k-1);
q*=inv;
q%=mod;
p*=inv;
p%=mod;
p=q-p;
p=(p+mod)%mod;
cout<<p<<" "<<q;
return 0;
}
|