T2：

　　很容易想到正难则反，只需要求解所有变量取值都不同的概率即可

古典概型，发现结果为A(2^n,m) / 2^nm，现在问题为对该式进行约分

分母可以快速幂求出，只要处理分子即可

　　需要注意的是，在约分过程中应先约分在取模，原因在于

同余类关于模数乘法不封闭，仅完全剩余系关于模数乘法封闭

因此在无法先约分在取模的情况下，我们就要考虑数学式本身的特点

发现分母为2^nm，因此只要约去所有2即可

　　这里考虑如何求A(2^n,m)中2的次数，对于2^n直接约去即可

引理：A(2^n,m) / 2^n中2的次数与(m - 1)!相同，考虑二进制表示下

2^x与x关系，只需二进制取反即可证明

因此我们只需要求出(m - 1)!中2的次数即可

　　对(m - 1)!中2次数的O(logn)经典求法：依次考虑m-1个数中

含2的数通过除2的次数删去，统计答案即可

代码如下：

 1 #include<bits/stdc++.h> //同余类关于模数乘法不封闭，完全剩余系关于模数乘法封闭
 2 using namespace std;
 3 #define I int
 4 #define LL long long
 5 #define C char
 6 const I mod = 1e6 + 3;
 7 inline LL read(){LL x(0);C z(getchar());while(!isdigit(z))z=getchar();while(isdigit(z))x=x*10+(z^48),z=getchar();return x;}
 8 LL n,m,one,two,three,tot;
 9 LL qpow (LL a,LL b) {
10     LL res(1),base(a);
11     while (b) {
12         if (b & 1) res = res * base % mod;
13         base = base * base % mod;
14         b >>= 1;
15     }
16     return res;
17 }
18 signed main () {
19     n = read(),m = read();
20     for (LL i(1);1ll << i < m; ++ i)
21       tot += (m - 1) / (1ll << i);
22     tot = qpow (2,tot);
23     tot = qpow (tot,mod - 2); 
24     one = qpow (2,n);
25     two = qpow (one,m - 1);
26     two = two * tot % mod;
27     three = 1;
28     one = one ? one - 1 : mod - 1;
29     if (m >= mod || one + 1 <= m - 1) three = 0;
30     else {
31       for (I i(one);i > one - m + 1; -- i)
32         three = three * i % mod;
33       three = three * tot % mod;
34     }
35     three = two - three;
36     if (three < 0) three += mod;
37     printf ("%lld %lld",three,two);
38 }

View Code