CF715C Digit Tree
2022/8/15 23:28:02
本文主要是介绍CF715C Digit Tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
沝黑。
首先这种统计路径的问题一般联想点分治,然后考虑如何处理经过一个点 \(u\) 的路径。
考虑有一个点 \(p\in u\) 的子树,然后记录路径 \(p\to u\) 和路径 \(u\to p\) 的答案。前者放入一个映射统计,后者存在数组 \(S\) 里面。
最后整体统计,枚举 \(x\in S\),设 \(x\lt M\),统计映射的 \(M-x\) 位置的结果,求一个和。
但是这样可能会有一条路径,从 \(u\) 的一个儿子 \(v\) 的子树来,又到 \(v\) 的子树去。
于是我们考虑分开对每个儿子做一次上述统计子树的算法,然后让 \(u\) 子树的总和减去每个 \(v\) 子树的总和即可。
中间会有把一个多位数和一个数字拼起来的情况,考虑记录下原数的位数,预处理 \(10\) 的次幂以及逆元。
对了,\(M\) 不一定是质数,所以不能用 \(x^{mod-2}\) 的方法求逆元,而是要用 \(\tt exgcd\)。
对了,unordered_map
会被卡,map
已经很够了。
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #include<bits/stdc++.h> using namespace std; #ifdef ONLINE_JUDGE static char buf[1000000],*p1=buf,*p2=buf; #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++ #endif inline int read(){ register int x = 0; register char c = getchar(); for(;c < '0' || c > '9';c = getchar()); for(;c >= '0' && c <= '9';c = getchar()) x = x * 10 + (c ^ '0'); return x; } #define rg register #define il inline #define rep(i,a,b) for(rg int i = (a);i <= (b);++i) #define Rep(i,a,b) for(rg int i = (a);i >= (b);--i) #define pb emplace_back using ll = long long; const int N = 1e5 + 5; int n,val,rt,allsiz,siz[N]; ll sum; int Mod,inv10,pow10[N],powinv10[N]; bitset<N> vis; vector<pair<int,int>> G[N]; map<int,long long> buc; vector<pair<ll,int>> num; il void exgcd(rg int a,rg int b,rg int &x,rg int &y){ if(!b) return x = 1,void(y = 0); exgcd(b,a % b,y,x); y -= a / b * x; } il int size(rg int u,rg int ft){ int res = 1; for(auto[v,w] : G[u]) if(!vis[v] && v != ft) res += size(v,u); return res; } il void fndrt(rg int u,rg int ft){ int ans = 0; siz[u] = 1; for(auto[v,w] : G[u]) if(!vis[v] && v != ft){ fndrt(v,u); siz[u] += siz[v]; ans = max(ans,siz[v]); } ans = max(ans,allsiz - siz[u]); if(ans < val) val = ans,rt = u; } il void dfs(rg int u,rg int ft,rg ll v1,rg ll v2,rg int len){ if(~len) ++buc[v1],num.pb(v2,len); for(auto[v,w] : G[u]) if(v != ft && !vis[v]){ ll val1 = (1LL * pow10[len + 1] * w % Mod + v1) % Mod; ll val2 = (v2 * 10 % Mod + w) % Mod; dfs(v,u,val1,val2,len + 1); } } il ll calc(rg int u,rg int p){ ll cnt = 0; buc.clear(); num.clear(); dfs(u,0,p % Mod,p % Mod,p ? 0 : -1); for(auto[x,d] : num){ ll v = (Mod - x) * powinv10[d + 1] % Mod; if(buc.find(v) != buc.end()) cnt += buc[v]; if(!p) cnt += !x; } if(!p) if(buc.find(0) != buc.end()) cnt += buc[0]; return cnt; } il void solve(rg int u){ vis[u] = 1; sum += calc(u,0); for(auto[v,w] : G[u]) if(!vis[v]){ sum -= calc(v,w); allsiz = size(v,0),val = 1e9,rt = 0,fndrt(v,0); solve(rt); } } int main(){ n = read(),Mod = read(); rep(i,1,n - 1){ int u,v,w; u = read(),v = read(),w = read(); ++u,++v; G[u].pb(v,w); G[v].pb(u,w); } int x,y; exgcd(10,Mod,x,y); inv10 = (x % Mod + Mod) % Mod; pow10[0] = powinv10[0] = 1; rep(i,1,n) pow10[i] = 10LL * pow10[i - 1] % Mod; rep(i,1,n) powinv10[i] = 1LL * inv10 * powinv10[i - 1] % Mod; allsiz = n,val = 1e9,rt = 0,fndrt(1,0); solve(rt); cout << sum << endl; return 0; }
这篇关于CF715C Digit Tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升