結果
問題 | No.2360 Path to Integer |
ユーザー |
![]() |
提出日時 | 2023-06-23 21:59:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,500 ms |
コード長 | 1,500 bytes |
コンパイル時間 | 2,104 ms |
コンパイル使用メモリ | 199,060 KB |
最終ジャッジ日時 | 2025-02-15 01:00:50 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;constexpr int mod = 998244353;void mpl(int &x,int y) {x += y;if(x >= mod) x -= mod;}int f[1000],dp1[100200],dp2[100200];int ans;pair<int,int> dfs(int n,int p,vector<string>&A,vector<vector<int>>&ki) {long long now = stoll(A[n])%mod;int cnt1 = 0,cnt2 = 0;for(int i:ki[n]) {if(i == p) {continue;}pair<int,int> a = dfs(i,n,A,ki);mpl(ans,1ll*dp1[n]*a.second%mod);mpl(ans,1ll*cnt1*dp2[i]%mod);mpl(ans,1ll*dp1[i]*cnt2%mod);mpl(ans,1ll*dp2[n]*a.first%mod);mpl(cnt1,a.first);mpl(cnt2,1ll*a.second*f[A[n].size()]%mod);mpl(dp1[n],1ll*dp1[i]*f[A[n].size()]%mod);mpl(dp1[n],now*a.first%mod);mpl(dp2[n],dp2[i]);mpl(dp2[n],now*a.second%mod);}mpl(dp1[n],now);mpl(ans,dp1[n]);mpl(ans,dp2[n]);mpl(dp2[n],now);cnt1++;mpl(cnt2,f[A[n].size()]);return {cnt1,cnt2};}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);f[0] = 1;for(int i = 1; i < 100; i++) {f[i] = f[i-1]*10ll%mod;}int N;cin >> N;vector<string>A(N);for(int i = 0; i < N; i++) {cin >> A[i];}vector<vector<int>>ki(N);for(int i = 0; i < N-1; i++) {int u,v;cin >> u >> v;u--;v--;ki[u].push_back(v);ki[v].push_back(u);}dfs(0,-1,A,ki);cout << ans << "\n";}