抽屉原理，快速幂，逆元，概率。
如果$k > {2^n}$，根据抽屉原理可知，答案就是$1$ $1$。
否则概率一定小于$1$，就要计算，公式很简单，上过概率论的应该都会算。
概率为：$1 - frac{{({2^n} - 0)*({2^n} - 1)*({2^n} - 2)*({2^n} - 3)*......*({2^n} - (k - 1))}}{{{2^{nk}}}}$ $ = 1 - frac{{({2^n} - 1)*({2^n} - 2)*({2^n} - 3)*......*({2^n} - (k - 1))}}{{{2^{n(k - 1)}}}}$。
下面我们来计算这一部分：$frac{{({2^n} - 1)*({2^n} - 2)*({2^n} - 3)*......*({2^n} - (k - 1))}}{{{2^{n(k - 1)}}}}$。
因为分母是$2$的幂次，所以分子和分母的$GCD$肯定是$2$的幂次。设$GCD={2^{tmp}}$。$tmp$的求法很简单，就是$1,2,3,4,5,...,k-1$这些数能被$2$整除的次数之和。
然后我们要将分子分母同时除以${2^{tmp}}$，可以转化为$×{2^{tmp}}$的逆元。
这个时候又遇到了一个难题：分子的项这么多，怎么求？
仔细思考一下会发现，分子是连续的$k-1$个数字相乘，如果$k-1>=mod$，根据抽屉原理可知，分子中必然有一个数字是$mod$的倍数。
也就是说，如果$k-1>=mod$，那么分子取模之后就是$0$；如果$k-1<mod$，那么暴力循环一遍算出分子就可以了。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } LL mod=1e6+3,pmod=mod-1; LL n,k; LL extend_gcd(LL a,LL b,LL &x,LL &y) { if(a==0&&b==0) return -1; if(b==0){x=1;y=0;return a;} LL d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d; } LL mod_reverse(LL a,LL p) { LL x,y; LL d=extend_gcd(a,p,x,y); if(d==1) return (x%p+p)%p; else return -1; } LL POW(LL a, LL b) { LL ans = 1; a %= mod; while(b) { if(b & 1) ans = ans * a % mod, b--; b >>= 1; a = a * a % mod; } return ans; } int main() { scanf("%lld%lld",&n,&k); LL u=1; bool flag=0; for(LL i=1;i<=n;i++) { u=u*(LL)2; if(k<=u) { flag=1; break; } } if(flag==0) printf("1 1 "); else { LL fz,fm; LL h=(n%pmod)*(((k%pmod)-1+pmod)%pmod)%pmod+pmod; fm=POW((LL)2,h); LL tmp=0; for(LL i=2;i<=k-1;i=i*2) tmp=tmp+(k-1)/i; LL GCD=POW((LL)2,tmp); LL NI=mod_reverse(GCD,mod); fm=fm*NI%mod; if(k-1>=mod) printf("%lld %lld ",fm,fm); else { fz=1; for(LL i=1;i<=k-1;i++) fz=fz*((POW((LL)2,n)-i+mod)%mod)%mod; fz=fz*NI%mod; fz=(fm-fz+mod)%mod; printf("%lld %lld ",fz,fm); } } return 0; }