CodeForces

Luogu翻译

分析

树上统计显然是点分治。

考虑怎么统计。设当前的根为$root$,根到$x$的路径上的数是$d_1$,根到$y$的路径上的数是$d_2$,根到$y$的距离(此时$y$的深度)为$dep$。

若$x\to y$这条路径合法,显然需要满足:

$d_1\cdot10^{dep}+d_2\equiv0\pmod m$

这样子不好搞,我们要把$d_2$和$dep$放到一起去。

因为$\gcd(10,m)=1$即$m$与$10$互质,所以可以把两边同时除以$10^{dep}$,得到:

$d_1+d_2\cdot10^{-dep}\equiv0\pmod m$

这样变得很好搞。$10^{-dep}$求个逆元就行,可以预处理一下$10$的幂。

用一个map来记录$d_1$,用pair来记录<d2,dep>这样的二元组。统计答案时枚举二元组,然后到map里找对应的数量累加即可。

注意,$0$也能被$m$整除。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#define re register
#define mp make_pair
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

int n,m;
struct Edge { int v,w,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int vis[MAXN];
int p[MAXN]; //p[i]=10^i
int sz[MAXN],f[MAXN],dep[MAXN];
int root,sum,ans,num;
map<int,int> s; //sum[d1]为d1的数量
pair<int,int> dig[MAXN<<1]; //<d2,dep>

inline void getroot(int u,int fa) {
    sz[u]=1,f[u]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (vis[v]||v==fa) continue;
        getroot(v,u); sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-f[u]);
    if (f[u]<f[root]) root=u;
}

inline void getdigit(int u,int fa,int d1,int d2,int d) {
    if (d>=0) ++s[d1],dig[++num]=mp(d2,d);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (v==fa||vis[v]) continue;
        int d3=(d1+w*p[d+1])%m;
        int d4=(d2*10+w)%m;
        getdigit(v,u,d3,d4,d+1);
    }
}

inline int exgcd(int a,int b,int& x,int& y) {
    if (!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,x,y);
    int z=x; x=y; y=z-a/b*y;
    return d;
}
inline int inv(int a,int m) { //a在mod m意义下的逆元
    int x,y,d=exgcd(a,m,x,y);
    return d==1?(x%m+m)%m:-1;
}

inline int calc(int u,int d) {
    s.clear(); int rt=0; num=0;
    if (d) getdigit(u,0,d%m,d%m,0);
    else getdigit(u,0,0,0,-1);
    for (re int i=1;i<=num;++i) {
        int tmp=(-dig[i].first * inv(p[dig[i].second+1],m) % m + m) % m;
        if (s.find(tmp)!=s.end()) rt+=s[tmp];
        if (!d) rt+=!dig[i].first;
    }
    if (!d) rt+=s[0]; //0也能被m整除
    return rt;
}

inline void solve(int u) {
    ans+=calc(u,0); vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (vis[v]) continue;
        ans-=calc(v,w);
        sum=sz[v],f[0]=n,root=0;
        getroot(v,u);
        solve(root);
    }
}

mainint main() {
    n=read(),m=read();
    for (re int i=1,u,v,w;i<n;++i) {
        u=read()+1,v=read()+1,w=read();
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    p[0]=1; for (re int i=1;i<=n;++i) p[i]=p[i-1]*10%m;
    f[0]=sum=n; getroot(1,0); solve(root);
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 13 PM