結果
問題 | No.2360 Path to Integer |
ユーザー |
|
提出日時 | 2023-06-23 22:05:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,500 ms |
コード長 | 1,081 bytes |
コンパイル時間 | 678 ms |
コンパイル使用メモリ | 76,772 KB |
実行使用メモリ | 19,780 KB |
最終ジャッジ日時 | 2024-07-01 01:42:07 |
合計ジャッジ時間 | 2,104 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; vector<int>G[1<<17]; int N; mint A[1<<17],p10[1<<17]; mint ans; mint dp[1<<17]; int ch[1<<17]; void dfs(int u,int p) { dp[u]=mint::raw(1); ch[u]=1; for(int v:G[u])if(v!=p) { dfs(v,u); dp[u]+=dp[v]; ch[u]+=ch[v]; } dp[u]*=p10[u]; } void dfs2(int u,int p,mint pdp) { mint ndp=dp[u]+pdp*p10[u]; for(int v:G[u])if(v!=p) { //ans+=(N-ch[v])*A[v]*(dp[v]/p10[v]); ans+=(N-ch[v])*A[u]*dp[v]; //ans+=ch[v]*A[u]*(ndp/p10[u]-dp[v]); ans+=ch[v]*A[v]*(ndp-dp[v]*p10[u]); dfs2(v,u,ndp-dp[v]*p10[u]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N; for(int i=0;i<N;i++) { string a; cin>>a; p10[i]=mint::raw(10).pow(a.size()); for(char c:a) { A[i]=mint::raw(10)*A[i]+mint::raw(c-'0'); } ans+=A[i]*N; } for(int i=1;i<N;i++) { int u,v;cin>>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } dfs(0,-1); dfs2(0,-1,mint::raw(0)); cout<<ans.val()<<endl; }