题解 P6274 [eJOI2017]六

搬运一下自己的博客

神仙思路。

~~对不起，爆搜真的能切题~~

状压套状压，对于每一个 $N$ 的因数，我们可以求出它带有哪些 $N$ 的质因数（注意，这里不要求质因数次数，因为两个数只要含有同一个质因数就不互质了）。然后用乘法原理优化一下就可以 $O(k2^k)$ 求出含有这些质因数的数的个数。

然后状压，三进制，$2^k-1$ 位，第 $i$ 位的值代表有多少个质因数情况为 $i$ 的。

这样可能不好理解，举个例子：

$N=2^2 \times 3^2 \times 5 \times 7$

所以 $k=4$ ，然后比如像 $84=2^2 \times 3 \times 7$ 很显然是 $N$ 的因数，此时质因数情况为 $1101$

然后记忆化搜索即可。

但是仍然需要优化，首先把 $3$ 进制变成 $4$ 进制更加好写，但是此时需要用两个 $unsigned \ \ long \ \ long$ 存，此时用 $map$ 又多一个 $log$ （虽然没多大事貌似），考虑使用 $hash$ ，就两位，还不用担心取模耗时间（ $ull$ ），然后貌似就可以了

细节看代码：

#include
#include

#define ull unsigned long long

#define maxn 101
#define maxN 20000002
#define mod 1000000007

inline long long read(){
    long long r=0,f=0;
    char c;
    while(!isdigit(c=getchar()))f|=(c=='-');
    while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return f?-r:r;
}

int k,cs[maxn],cnt[maxn],rel[maxn][maxn];

long long n,m,p[maxn],f[maxN];//f尽量开大，hash冲突概率小一些

inline void add_cnt(long long x){
    int zt=0;
    for(int i=0;i>(i<<1)):(y>>((i-32)<<1)))&3;
}

inline void add(ull &x,ull &y,int i){
    i<32?x+=1ull<<(i<<1):y+=1ull<<((i-32)<<1);
}

long long solve(ull x,ull y){
    ull hx=x*131+y;//hash
    hx%=maxN;
    if(f[hx])return f[hx];
    long long ans=1;
    for(int i=1;i<(1<1)cs[k]=1,p[k++]=m;
    for(int i=1;i<(1<>j)&1)cnt[i]*=cs[j];
    }
    printf("%lld",(solve(0,0)-1+mod)%mod);//记得减1，因为不能不放数字
    return 0;
}