P5366 [SNOI2017] 遗失的答案

· · 个人记录

当仁不让 希言自然 莫向外求 气冲斗牛 ——题记

题意

数据范围

解析

0.题意转化

1.dp 设计

2.针对询问的 dp 修正

示范代码

#include<bits/stdc++.h>
#define il inline
#define ri register
#define For(i,a,b) for(ri int i=(a);i<=(b);++i)
#define foR(i,a,b) for(ri int i=(a);i>=(b);--i)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define b_s basic_string
#define u_map unordered_map
#define pii pair<int,int>
#define m_p make_pair
#define fir first
#define sec second
#define nsync ios::sync_with_stdio(0),cin.tie(0)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
il ll rd(){
    ll x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
char wtst[66];
int wtps;
il void wt(ll x){
    if(x<0) putchar('-'),x=-x;
    while(x>9) wtst[++wtps]=(x%10+'0'),x/=10;
    wtst[++wtps]=x+'0';
    while(wtps) putchar(wtst[wtps--]);
}
il void wtk(ll x){wt(x);putchar(' ');}
il void wth(ll x){wt(x);putchar('\n');}

const int maxp=1e4+7,usep=1e4;
bitset<maxp> np;
int p[maxp],nump;
il void euler(){
    np[0]=np[1]=1;
    For(i,2,usep){
        if(!np[i]) p[++nump]=i;
        for(ri int j=1;j<=nump && i*p[j]<=usep;++j){
            np[i*p[j]]=1;
            if(!(i%p[j])) break;
        }
    }
}

int N,G,L;
int usen,useg,usel;

int pf[9],numpf,numpf2;//prime factor
int lt[9];
int full;

const int maxf=769;
struct factor{
    int v,sta;
    bool operator<(const factor &b)const{return v<b.v;}
}f[maxf];
int numf;
u_map<int,short> refl;
il void init(){
    N=rd(),G=rd(),L=rd();
    usen=N/G,usel=L/G,useg=G/G;
    //基本读入

    euler();
    int nowl=usel,t=0;
    For(i,1,nump){
        while(!(nowl%p[i])) ++t,nowl/=p[i];
        if(t) pf[++numpf]=p[i],lt[numpf]=t,t=0;
    }
    if(nowl>1) pf[++numpf]=nowl,lt[numpf]=1;//注意这里是从 1 开始存的，实际使用中必须减 1 
    numpf2=(numpf<<1),full=(1<<numpf2)-1;
    //对 L 质因数分解

    int usei,tnow[9];
    for(ri int i=1;i*i<=usel && i<=usen;++i)
        if(!(usel%i)){
            usei=i; mem(tnow,0);
            f[++numf].v=usei;
            For(j,1,numpf){
                while(!(usei%pf[j])) ++tnow[j],usei/=pf[j];
                f[numf].sta=f[numf].sta|((!tnow[j])<<(numpf2-j))|((tnow[j]==lt[j])<<(numpf-j));
            }

            usei=usel/i; 
            if(usei==i || usei>usen) continue;
            f[++numf].v=usei;
            For(j,1,numpf){
                tnow[j]=lt[j]-tnow[j];
                f[numf].sta=f[numf].sta|((!tnow[j])<<(numpf2-j))|((tnow[j]==lt[j])<<(numpf-j));
            }
        }
    sort(f+1,f+1+numf);
    For(i,1,numf) refl[f[i].v]=i;
    //生成所有约数 
}

const int lim=(1<<16),mod=1e9+7;//够不到 
int dpf[maxf][lim],dpb[maxf][lim];//ll 根本开不开，必须步步模 //f 从左向右，b 从右向左 
bitset<lim> vis;
il void add(int &a,int b){a=a+b; if(a>=mod) a=a-mod;}//大胆一点。 
il void DP(){
    dpf[0][0]=1;
    For(i,0,numf-1)
        For(sta,0,full)
            if(dpf[i][sta]){
                add(dpf[i+1][sta],dpf[i][sta]);
                add(dpf[i+1][sta|f[i+1].sta],dpf[i][sta]);
            }
    //正向

    dpb[numf+1][0]=1;
    foR(i,numf+1,2)
        For(sta,0,full)
            if(dpb[i][sta]){
                add(dpb[i-1][sta],dpb[i][sta]);
                add(dpb[i-1][sta|f[i-1].sta],dpb[i][sta]);
            }
    //反向 
}

int ans[maxf];
int sum[maxf][lim];
il void work(){
    int stanow;
    for(ri int l=0,i=1,r=2;i<=numf;++l,++i,++r){
        if(r<=numf) For(sta,0,full) sum[r][sta]=dpb[r][full^sta];
        else sum[r][full]=1;
        For(j,0,numpf2-1)
            For(sta,0,full)
                if(sta&(1<<j))
                    add(sum[r][sta],sum[r][sta^(1<<j)]);

        For(sta,0,full)
            if(dpf[l][sta]){
                stanow=(sta|f[i].sta);
//              fsta=(stanow^full);//取两遍反，相当于没取 
                add(ans[i],1ll*dpf[l][sta]*sum[r][stanow]%mod);
            }
    }
}

il void answer(){
    int Q=rd(),x;
    while(Q--){
        x=rd();
        if(x%G || L%x){wth(0); continue;}
        x=x/G;
        wth(ans[refl[x]]);
    }
}

int main(){
    init();
    DP();
    work();
    answer();
    return 0;
}
/*
首先，我们将题意转化。 
若 G>1，则将 N,L,G 同除 G 
显然，N%G!=0 部分不可能被选，故此变换等价 
只要在询问时处理一下即可。

接下来我们对 L 做质因数分解。
打表可得 1e8 一定拆不出来 23(在尽量让不同质因数尽量多的前提下) 
故不同的质因数至多为 2 3 5 7 11 13 17 19，即 8 种，记为 P 
由约数个数定理随便乱搞一下，容易发现，
不同的约数至多有 768 种，记为 D 
有了这些，我们就有能力度量复杂度了。

基于 gcd 和 lcm 的实质，考虑一个简单 dp：
dp[i][sta1][sta2] 表示考虑完毕了前 i 个约数，sta1 表示各个质因子是否有 0 次方，sta2 表示各个质因子是否有 max 次方，内容为总方案数。
则实际上的状态大小为 D*2^P*2^P=D*2^2P=4e7

考虑如何转移。预处理出每个约数及其质因数分解。
进一步地，我们可以给每个约数整个 state1,state2 表示对应质因子是否为 0 次方，是否为 max 次方。
这一部分显然不是复杂度瓶颈。
于是递推转移为 dp[i][sta1][sta2]->dp[i+1][~][~] 以及 dp[i+1][sta1|state1][sta2|state2]
固然可以写转移方程，但是我们知道这样递推因为带 if 可能常数小一点 
则我们有了一个 O(1) 的转移。故，总复杂度为 4e7 

考虑如何回答询问。容易想到一个简单的暴力：强制选择这个数然后暴力 DP
当然，我们知道，这是绝无希望能过的。所以，
考虑一个稍微能接受一点的做法：
离线询问。 
从左向右、从右向左分别 DP，
对于每个询问，在它左边枚举，在它右边枚举，加上它自己的 state，合法则合法。
然而不能接受，这个枚举的复杂度是 2^4P=2^32
所以考虑只枚举一边，复杂度骤降至单个询问 2^2P，故总复杂度为 D*2^2P，与 DP 同阶
只枚举一边之后，我们就得到了一个当前的 state，譬如 100 001
从而对面必须是 x11 11x，即 011 110 的超集
显然这个东西长得不美妙，所以我们得把两个 sta 合到一起，规定 GCD 的在前面 

现在的问题就变成了对于给定的二进制数，怎么求它的超集和。
复杂度要求...对于所有的二进制数总共是 O(2^2P)，毕竟外面还有一个 D，你可能得对于每个约数都求一遍，当然这里才 4e7 有些冗余的 
超集我不会，转成子集试试
将第二个 DP 的 sta 取反，则 011110 的超集和就变成了 100001 的子集和。
还算能接受，我去接杯水，等下继续

显然暴力枚举所有子集根本行不通，那跟刚才的没区别
所以得考虑一点带递推性质或者别的什么的东西
我们知道这实际上好像是 FMT，但没关系。

考虑这样递推它：
先把子集和拆成以下几部分：
只有第 0 位(位权 1)不一样的，只有第 1 位不一样的，...,etc.，记为 just[i][sta]，表示对 sta 来说只有第 i 位不一样的子集的和 

众所周知，"恰好"在信竞中约等于不可做
所以先把它转成
第 0 位及以下不一样的，第 1 位及以下不一样的，...,etc.，记为 sum[i][sta]，容易看出有 sum[i][sta]=sum[i-1][sta]+just[i][sta] 

接下来分类讨论这个 just 怎么处理
当 sta&(1<<i)==0，显然有 just[i][sta]=0，即 sum[i][sta]=sum[i-1][sta]
当 sta&(1<<i)==1，啊，这就有点难办了
举个例子会比较显然。对于 111 来说
just-1(完全一样): 111
just0: 110 
just1: 100 101
just2: 000 010 001 011
观察到什么了吗？不显然吗？那再看一下 just2
发现，just[2][111]=sum[1][11] ! 
从而似乎可以递推。sum[i][sta]=sum[i-1][sta]+sum[i-1][sta^(1<<i)]
OK，复杂度为 2P*2^(2P) 
总纸面复杂度 8e8，但是时限 2s
更进一步地这个做法常数不大，很有希望过 
*/

总结与反思

1.知识点

2.解题中的失误

3.其他

后记