题解
有些难度
对于 (30pts) 直接暴力
对于 (70pts) 发现规律 (2^n-a) 与 (a;;(ain [1,2^n))) 分解质因数后,(2) 的次数相同
(100pts)
对于至少有两个数相同,我们可以转化为 (1-p( ext{所有数均不相同})),那么 (p( ext{所有数均不相同})=frac{A_{2^n}^m}{2^{nm}})
对于这个式子,我们发现,上下能约分的因子只有 (2),根据上文,我们可以把求 (A_{2^n}^m) 质因子中 (2) 的次数转化为求 ((m-1)!) 中的
那么对于这个求 ((m-1)!) 中的 (2) 的次数可以 (logm) 求,具体做法是
for (register int i(2);i<m;i<<=1) cnt2+=(m-1)/i;
证明:
当 (i=2) 时,我们可以把 cnt2+=(m-1)/i
看成求 (1~m-1) 中有多少个数质因子中至少有一个 (2),其他情况同理
然后再根据逆元求即可
记得开 long long
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define int long long
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
static const int MOD=1e6+3;
int bs,n,m,cnt2,fz,fm;
inline int fpow(int a,int b) {
int res=1;
while(b) {
if (b&1) res=res*a%MOD;
a=a*a%MOD;b>>=1;
}
return res;
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
// printf("%lld
",fpow(2,1e6+1));
read(n),read(m);
if (log2(m)>(double)n) {puts("1,1");return 0;}
bs=fpow(2,n);
fm=fpow(bs,m-1);
if (m<=MOD) {
fz=1;
for (ri i(1);i<m;p(i)) fz=fz*(bs-i+MOD)%MOD;
}
for (register int i(2);i<m;i<<=1) cnt2+=(m-1)/i;
int inv=fpow(fpow(2,cnt2),MOD-2);
fz=fz*inv%MOD,fm=fm*inv%MOD;
printf("%lld %lld
",(fm-fz+MOD)%MOD,fm);
return 0;
}
#undef int
}
int main() {return nanfeng::main();}
证明一下 (2^n-a) 与 (a) 分解质因数后,(2) 的次数相同:
(2^n) 的二进制可以表示为 (10000...0),(1) 后面 (n) 个 (0),那么对于 (a),其二进制下最低一位 (1) 所对应的 (2^n) 的那一位一定为 (0)
那么,(2^n-a) 的最低一位 (1) 一定与 (a) 的相同,而最低一位 (1) 代表它分解质因数后 (2) 的次数为几。
举例:
(n=5,a=11),则 (n=100000),(a=1011),(2^5-a=10101)