首页 > 代码库 > CF715C:Digit Tree
CF715C:Digit Tree
传送门
一句话怎么说来着
算法+高级数据结构=OI
现在我感觉到的是
我会的算法+我会的高级数据结构=WA
这道题提交了三四十次，从刚看题到完全写好花了好几天..，主要死于看错费马小定理的适用条件。
下面是正经题解:
首先，这道题的难点不在于找到有多少个路径（很明显的点分治），而是判断一条路径是否合法。
按照点分治的一般套路。我们可以求出从一个点出发的所有路径，然而把所有路径组合起来就好了。
显然，对于把从$root$到所有子节点的路径的那个数只要不断的乘上去然后$modM$就行了。
所有我们面临的最主要的问题就是如何把两条路径组合起来。
首先，这里指的路径并不是两条完全相同的路径。比如说我们要验证从$node_i$经$root$到$node_j$的路径，我们应该求出$node_i \rightarrow root$数和$root \rightarrow node_j$的数。
不妨设这两个数的为别为$num_i$和$num_j$,把他们的长度（或者说是从根到$node$的深度）即为$deep_i$和$deep_j$，显然，如果$node_i \rightarrow node_j$的路径是合法的，我们可以得到以下关系。
$num_i+num_j \times 10^{deep_j} \equiv 0 (mod M)$
转换一下
$num_i \equiv -num_j \times 10^{-deep_j} (mod M)$
对于这个式子右边的，dfs一遍后用map存储即可。然后累加式子左边的即可。同时，要注意从统计式子右边完后，要-1，具体为什么实现的时候自己就能明白。
同时，$M$不一定为素数，所以这个模的意义一定要用乘法逆元或者欧拉函数什么的求，直接快速幂$M-2$会有问题。
1 //CF 716E 2 //by Cydiater 3 //2016.9.27 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <queue> 9 #include <map> 10 #include <ctime> 11 #include <cmath> 12 #include <string> 13 #include <cstdio> 14 #include <cstdlib> 15 #include <iomanip> 16 using namespace std; 17 #define ll long long 18 #define up(i,j,n) for(int i=j;i<=n;i++) 19 #define down(i,j,n) for(int i=j;i>=n;i--) 20 const int MAXN=1e6+5; 21 const int oo=0x3f3f3f3f; 22 inline ll read(){ 23 char ch=getchar();ll x=0,f=1; 24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 26 return x*f; 27 } 28 map<ll,ll>cnt; 29 ll N,mod,LINK[MAXN],len=0,pow10[MAXN],inv10[MAXN],root,sum,siz[MAXN],max_siz[MAXN],ans=0,dis[MAXN],deep[MAXN]; 30 struct edge{ 31 ll y,next,v; 32 }e[MAXN]; 33 bool vis[MAXN]; 34 namespace solution{ 35 inline void insert(ll x,ll y,ll v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} 36 inline ll quick_pow(ll a,ll b){ 37 ll tmp=1; 38 while(b){ 39 if(b&1)tmp=(tmp*a)%mod; 40 b>>=1;a=(a*a)%mod; 41 } 42 return tmp; 43 } 44 void make_root(int node,int fa){ 45 siz[node]=1;max_siz[node]=0; 46 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){ 47 make_root(e[i].y,node); 48 siz[node]+=siz[e[i].y]; 49 max_siz[node]=max(max_siz[node],siz[e[i].y]); 50 } 51 max_siz[node]=max(max_siz[node],sum-max_siz[node]); 52 if(max_siz[node]<max_siz[root])root=node; 53 } 54 void ex_gcd(ll a,ll b,ll &x,ll &y){ 55 if(b==0){x=1;y=0;return;} 56 ex_gcd(b,a%b,x,y); 57 ll t=x;x=y;y=t-a/b*y; 58 } 59 ll get_inv(ll num){ 60 ll x,y; 61 ex_gcd(num,mod,x,y); 62 return ((x%mod+mod)+mod)%mod; 63 } 64 void init(){ 65 N=read();mod=read(); 66 up(i,2,N){ 67 ll x=read()+1,y=read()+1,v=read(); 68 insert(x,y,v); 69 insert(y,x,v); 70 } 71 if(mod<=1){ 72 cout<<N*(N-1)<<endl; 73 exit(0); 74 } 75 pow10[0]=1; 76 up(i,1,N)pow10[i]=(pow10[i-1]*10)%mod; 77 up(i,0,N)inv10[i]=get_inv(pow10[i]);//pret 78 } 79 void dfs(ll node,ll fa){ 80 ll tmp=(((mod-dis[node])%mod+mod)*inv10[deep[node]]+mod)%mod; 81 cnt[tmp]++; 82 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){ 83 dis[e[i].y]=((dis[node]*10)%mod+e[i].v)%mod; 84 deep[e[i].y]=deep[node]+1; 85 dfs(e[i].y,node); 86 } 87 } 88 ll get_ans(int node,int fa){ 89 ll tmp=cnt[dis[node]%mod]; 90 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){ 91 deep[e[i].y]=deep[node]+1; 92 dis[e[i].y]=(dis[node]+(e[i].v*pow10[deep[node]])%mod)%mod; 93 tmp+=get_ans(e[i].y,node); 94 } 95 return tmp; 96 } 97 ll col(int node,ll dist,int dep){ 98 dis[node]=dist%mod;deep[node]=dep; 99 dfs(node,0);100 cnt[0]--;101 return get_ans(node,0);102 }103 void work(int node){104 vis[node]=1;105 cnt.clear();106 ans+=col(node,0,0);107 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){108 cnt.clear();109 ans-=col(e[i].y,e[i].v,1);110 root=0;sum=siz[e[i].y];111 make_root(e[i].y,0);112 work(root);113 }114 }115 void slove(){116 root=0;max_siz[root]=oo;sum=N;117 make_root(1,0);118 work(root);119 }120 void output(){121 cout<<ans<<endl;122 }123 }124 int main(){125 //freopen("input.in","r",stdin);126 using namespace solution;127 init();128 slove();129 output();130 }131
CF715C:Digit Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。