NOIP 模拟 $12\; \text{简单的玄学}$

题解

有些难度

对于 $30pts$ 直接暴力

对于 $70pts$ 发现规律 $2^n-a$ 与 $a\;\;(a\in [1,2^n))$ 分解质因数后，$2$ 的次数相同

$100pts$

对于至少有两个数相同，我们可以转化为 $1-p(\text{所有数均不相同})$，那么 $p(\text{所有数均不相同})=\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\n",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\n",(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$

巴特西

NOIP 模拟 $12\; \text{简单的玄学}$

题解

最新文章

热门文章