codeforces-711e-ZS and The Birthday Paradox-数论-勒让定理

题目链接

题意：设一年有2^n个日子，现在有k个人，求至少有两个人在同一天的概率是多少，写成A/B（A,B互质）这样的格式，之后再对1e6+3取模。

思路：很简单的就能想到，只要求所有人的生日都不在同一天的概率，拿1减就行了。如果2^n<k，那么必然有两个人在同一天，输出“1 1”即可。

如果2^n>=k，那么分子为k!c(2^n,k)，这是所有人不在同一天的情况。分母为2^(kn),这是总的情况。
化简一下分子是∏（2^n-i），i=1,2…k-1、
分母是2^(k-1)n

如果仅仅是这样的话，这题就是个大水题了。
但是n,k都巨大，要取模，所以这题就变得十分困难。
首先上下要同除以公因式。观察一下，分母是2的幂次，所以公因式一定是2的幂次。看分子，2^n-i，当且仅当i是2的幂次时，这个式子才对公因式有贡献。所以一个简单的想法是把所有的i都算一遍加在一起记为cnt，上下同乘cnt对于mod的逆元就行了，正好，当k-1>=mod的时候，分子一定为零，直接输出1 1就行，k-1<mod的时候可以暴力求分子，是不是感觉很美妙？
然而事实证明这是个sb想法……第四个数据就wa了……
错在了顺序，题目要求先除以公因式，再取模，而上面的做法是取模之后再除以公因式。
那么，怎么样求1,2……k-1中2的幂次乘积呢？、
题解提供了一个叫勒让德定理的东西
链接在这勒让德定理

虽然不知道具体怎么证的，反正就开心的用啦，用完就神奇的ac啦。
好吧，完全没有上进心。
代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long mod=1000000+3;
long long pp(long long a,long long b)
{
	long long ans=1;
	a=a%mod;
	while(b>0)
	{
		if(b%2==1)
		ans=ans*a%mod;
		b=b/2;
		a=a*a%mod;
	}
	return ans%mod;
}
int main()
{
    long long i,j,k,m,n,a,b;
	scanf("%lld%lld",&n,&k);
	long long temp=1;
	int flag=0;
	for(int i=1;i<=n;i++)
	 {
	 	temp*=2;
	 	if(temp>=k)
	 	{
	 		
	 		flag=1;
	 		break;
		 }
	 }
	 if(flag==0)
	 {
	 	printf("1 1\n");
	 	return 0;
	 }
	 
    temp=0;
    
	if(k-1>=mod)
	{   long long temp=0;
	    long long kk=k-1;
	    long long p=2;
	    while(p<=kk)
	    {
	    	temp=(temp+(k-1)/p);
	    	p*=2;
		}
		long long b=pp(2,n);
		temp=pp(2,temp)%mod;
		b=pp(b,k-1)%mod*pp(temp,mod-2)%mod;
		printf("%lld %lld\n",b,b);
	    return 0;
	}
	 
	temp=0;
	long long kk=k-1;
	long long p=2;
    while(p<=kk)
	    {
	    	temp=(temp+(k-1)/p);
	    	p*=2;
		}
		
	//printf("temp %lld\n",temp);
    long long aa=pp(2,n);
    //printf("aa %lld\n",aa);
    a=1;
    b=1;
	for(int i=1;i<=k-1;i++)
	{
	  	a=a*(aa-i)%mod;
	}
	long long tt=pp(2,temp);
	//printf("tt:%lld\n",tt);
	a=a*pp(tt,mod-2)%mod;
	b=pp(2,n);
	b=pp(b,k-1);
	b=b*pp(tt,mod-2)%mod;
	
	a=b-a;
	a=(a+mod)%mod;
	printf("%lld %lld\n",a,b);
	return 0;	  
}