题解 P13046 [GCJ 2021 Finals] Divisible Divisions

· · 题解

爱来自重庆友谊联赛模拟赛。

温馨提示：这是一个和数学完全无关的做法，非常不好写，理论时间复杂度和题解区普遍解法的时间复杂度相同但常数极大。最大点用时 7s 左右。

闲话：考试时这个题的时间限制是 3s，所以本人只获得了 20 分，是一个比朴素算法还低的分数。

分析

统计方案数考虑动态规划，f_{i,0/1} 表示在第 i 位的结尾处分割，最后一段数字不合法或合法的方案数。

设 j 是上一个分割的位置，如果 (j,i] 这一段组成数字为 D 的倍数，则 f_{i,1} = \sum\limits_{j} f_{j,0} + f_{j,1}（意为当前段合法则上一段是否合法都可），否则 f_{i,0} = \sum\limits_{j} f_{j,1}（意为当前段不合法上一段必须合法）。

逐渐向前枚举 j 计算这一段数是否为 D 的倍数，并同时更新 f_i，时间复杂度 O(TL^2)，可以通过第一个子任务。

对于每一个 i 去枚举 j 的操作太慢了，需要优化，设 h_i 表示长度为 i 的前缀模 D，(j,i] 是 d 的倍数的充要条件是 h_i - 10^{i-j}h_j \equiv 0\pmod{D}。

经过变形可以得到：

h_i \equiv 10^{i-j}h_j\pmod{D}\\ \frac{h_i}{10^i} \equiv \frac{h_j}{10^j}\pmod{D}

当 D 与 10 互质，即 \gcd(10,D)=1 时，10 存在乘法逆元，把键值丢到 std::map 或 std::unordered_map 存起来，可以做到 O(TL \log L) 或 O(TL) 的时间复杂度。

如果这俩数不互质，即不存在 10 的乘法逆元，且你完全没有同余数论这方面的能力，这个方法是毫无前途的。

回归观察本身的式子 h_i \equiv 10^{i-j}h_j\pmod{D}，可以简单理解为 i 每次加一，前面的 h_j 都要乘以 10。又因为 h_i \in [0,D)，可以求出每种 h_i 乘 10 以后的值。

对其进行图论建模，对于每个 h 建立有向边 h \rightarrow 10h \bmod D。这个图有一个很好的性质，每个点的入度都恰好为 1，所以这个图是内向基环树森林。

对于每个 h_i 就有下列两种情况：

在环上

在环上找任意一个点断开拍平，不需要倍长，设环长为 E，按遍历顺序依次编号为 [0,E)，设为 s。

设 u = h_i,v = h_j，(j,i] 段合法的条件是 s_u - s_v \equiv i-j \pmod{E}，整理得 s_u - i \equiv s_v -j \pmod{E}，即对于同一个环，(s_u - i) \bmod E 相同的值，都是倍数。

在树上

预处理出树上每一个点到环上最近点的距离，可以看成把环缩成一个点，距离即节点深度，设为 d。

设 u = h_i,v = h_j，(j,i] 段合法的条件是 v 在 u 的子树中，且 d_v - d_u = i-j，整理得 i + d_u = j + d_v。

对于子树限制可以在 DFS 序上处理，于是转化为了二维数点问题，可以用树状数组单点修改区间查询维护。

对于树上的点，会在 i + d_u 的时刻到达环上开始循环，用一个 std::vector 记录每个时刻有多少个树上的点到达环上，加入即可。

只对 (j,i] 是倍数的计数，对所有 DP 值进行求和，用所有减去是倍数的即可得到不是倍数的。

建图和对基环树处理时间复杂度 O(D)，树上有用的点和限制最多 O(L) 个，所以对树上点做计数问题时间复杂度 O(L \log L)，总体时间复杂度 O(T(D + L \log L))。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 100005
#define MAXD 1000005
#define int unsigned
using namespace std;
typedef unsigned long long ULL;
constexpr int mod=1000000007;
struct PII{//压位 pair<int,int> 自动取模，可以忽略这段部分。
    ULL dt;
    PII(const ULL&_dt=0):dt(_dt){}
    PII(const int _first,const int _second):dt((ULL)_first<<32|_second){}
    PII operator ()(){dt>=((ULL)mod<<32)&&(dt-=(ULL)mod<<32),(dt&0xffffffffu)>=mod&&(dt-=mod);return *this;}
    PII operator + (const PII&B)const{return PII(dt+B.dt)();}
    PII operator - (const PII&B)const{return PII(dt+((ULL)mod<<32|mod)-B.dt)();}
    PII operator += (const PII&B){return *this=*this+B;}
    int first(){return dt>>32;}
    int second(){return dt&0xffffffffu;}
};
char s[MAXN];
int n,d,h[MAXN];
int p[MAXD];
vector<int> G[MAXD];
vector<PII> D[MAXD];
vector<pair<int,PII> > T[MAXN];
bool rg[MAXD];
int tot,in[MAXD],ou[MAXD],rn[MAXD],cy=0,dep[MAXD],sc[MAXD],rt[MAXD];
void dfs(const int u,const int r){
    rn[u]=cy,rt[u]=r,in[u]=++tot;
    for(const int v:G[u])dep[v]=dep[u]+1,dfs(v,r);
    ou[u]=tot;
}
struct BIT{
    vector<int> rk;
    vector<PII> b;
    void clear(){rk.clear(),b.clear();}
    void init(){
        sort(rk.begin(),rk.end()),rk.erase(unique(rk.begin(),rk.end()),rk.end());
        b.resize(rk.size());
    }
    int get(const int x){return lower_bound(rk.begin(),rk.end(),x)-rk.begin()+1;}
    void add(int x,const PII&v){for(;x<=(int)b.size();x+=x&-x)b[x-1]+=v;}
    PII ask(int x){PII ret(0,0);for(;x;x^=x&-x)ret+=b[x-1];return ret;}
}B[MAXN+MAXD];//每个不同的 i+d_u 分别求解。
void solve(const int test){
    cin>>(s+1)>>d,n=strlen(s+1);
    *h=0;
    for(int i=1;i<=n;i++) h[i]=(h[i-1]*10+(s[i]^'0'))%d;//计算前缀值。
    for(int i=0;i<d;i++) rg[i]=1,in[i]=rn[i]=sc[i]=rt[i]=dep[i]=0;
    for(int i=0;i<d;i++) ++in[p[i]=i*10%d];//计算入度。
    for(int i=0;i<d;i++) G[i].reserve(in[i]);
    static int Q[MAXD];//手写队列进行拓扑排序，能进行排序的都是树上点，否则是环上点。
    int ql=1,qr=0;
    for(int i=0;i<d;i++) !in[i]&&(Q[++qr]=i);
    for(int u;ql<=qr;){
        u=Q[ql++],G[p[u]].push_back(u),rg[u]=0;//对于环上点加入图中。
        !--in[p[u]]&&(Q[++qr]=p[u]);
    }
    cy=tot=0;
    for(int i=0;i<d;i++)if(rg[i]&&!rn[i]){
        int m=0;++cy;
        for(int u=i;!rn[u];u=p[u]) dfs(u,u),sc[u]=m++;
        D[cy].assign(m,PII(0,0));
    }
    for(int i=2;i<=n+d;i++) B[i].clear();
    for(int i=1,u;i<=n;i++)if(!rg[u=h[i]]) B[i+dep[u]].rk.push_back(in[u]);//有用的点加入。
    for(int i=2;i<=n+d;i++) B[i].init();//离散化，初始化树状数组。
    D[1]={PII(0,1)};//第一个环必为 0 形成的自环。
    PII s(0,1),f(0,0);//总和和当前值，first 键值为 f_{i,0}，second 键值为 f_{i,1}，默认在最前面进行的切割是合法的。
    for(int i=1,u;i<=n;i++){
        f=PII(0,0),u=h[i];
        for(const auto&[x,y]:T[i]){//加入第 i 时刻到环上的点。
            int z=D[rn[x]].size();
            D[rn[x]][(i+z-sc[rt[x]]%z)%z]+=y;
        }
        T[i].clear(),T[i].shrink_to_fit();。
        if(rg[u]){//在环上。
            int z=D[rn[u]].size();
            PII&v=D[rn[u]][(i+z-sc[u]%z)%z];
            f=PII(s.second()+mod-v.second(),v.first()+v.second())();
            v+=f;
        }
        else{//在树上。
            int id=i+dep[u];
            PII v(B[id].ask(B[id].get(ou[u]+1)-1)-B[id].ask(B[id].get(in[u])-1));
            f=PII(s.second()+mod-v.second(),v.first()+v.second())();
            B[id].add(B[id].get(in[u]),f);
            if(i+dep[u]<=n) T[i+dep[u]].emplace_back(u,f);
        }
        s+=f;
    }
    for(int i=0;i<d;i++) G[i].clear(),G[i].shrink_to_fit();
    cout<<"Case #"<<test<<": "<<((f.first()+f.second())%mod)<<'\n';
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int T;cin>>T;
    for(int _=1;_<=T;_++) solve(_);
    return 0;
}