Codeforces711E. ZS and The Birthday Paradox【數學題】

E. ZS and The Birthday Paradox

【題目描述】

傳送門

【題解】

我們最後可以得到一個式子 1 − A ( 2 n , k ) 2 n k 1-\frac{A(2^n,k)}{2^{nk}} 1−2nkA(2n,k)​

然後對這個式子拆分 1 − ( 2 n − k + 1 ) ( 2 n − k + 2 ) . . . ( 2 n − 1 ) / 2 n ( k − 1 ) 1-(2^n-k+1)(2^n-k+2)...(2^n-1)/2^{n(k-1)} 1−(2n−k+1)(2n−k+2)...(2n−1)/2n(k−1)

因為分母隻有2這個素因子，是以隻要求出分子中2的個數就可以了。

我們知道 g c d ( 2 n − k , 2 n ) = g c d ( k , 2 n ) gcd(2^n-k,2^n)=gcd(k,2^n) gcd(2n−k,2n)=gcd(k,2n)，是以我們隻需要求 ( k − 1 ) ! (k-1)! (k−1)!中2的質因子個數。

然後對于分子直接暴力求，肯定不會超過MOD次就會遇到x%MOD==0，是以複雜度可以保證。

【代碼如下】

#include<cstdio>
using namespace std;
typedef long long LL;
const int MOD=1e6+3;
LL N,K,N2,TMP,Num,A,B;
LL qsm(LL x,LL b){LL Mul=1;for(;b;b>>=1,x=x*x%MOD) if(b&1) Mul=Mul*x%MOD;return Mul;}
bool check(){for(LL i=1,x=1;i<=N;i++) if((x*=2)>=K) return 0;return 1;}
int main(){
	scanf("%lld%lld",&N,&K);
	if(check()){printf("1 1\n");return 0;}
	for(LL i=K-1;i;i>>=1) Num+=i/2;TMP=1;N2=qsm(2,N);
	for(LL i=1;i<K&&TMP;i++) TMP=TMP*(N2-i)%MOD;
	LL INV=qsm(qsm(2,Num),MOD-2);
	A=TMP*INV%MOD,B=qsm(N2,K-1)*INV%MOD;A=(B-A+MOD)%MOD;
	printf("%lld %lld\n",A,B);
	return 0;
}