結果
問題 | No.1878 union-find の数え上げ |
ユーザー |
|
提出日時 | 2022-03-18 22:14:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,568 bytes |
コンパイル時間 | 3,318 ms |
コンパイル使用メモリ | 231,388 KB |
実行使用メモリ | 10,180 KB |
最終ジャッジ日時 | 2024-10-03 09:41:49 |
合計ジャッジ時間 | 4,288 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 8 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,b) for(int i=b-1;i>=0;i--)#define rbit(i,a) for(int i=0;i<(1<<a);i++)#define all(x) (x).begin(),(x).end()template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }typedef long long ll;typedef long double lld;using namespace std;using namespace atcoder;using mint=static_modint<1000000007>;const ll mod=998244353;//const ll mod=1e9+7;int dx[4]={1,0,-1,0};int dy[4]={0,1,0,-1};const string zton="0123456789";const string atoz="abcdefghijklmnopqrstuvwxyz";ll gcd(ll a,ll b){ll r;r=a%b;if(r==0){return b;}else{return gcd(b,r);}}typedef pair<ll,int> P;vector<int> G[101010];int N;ll dp[101010][2];void dfs(int cu,int pa){bool f=false;for(int to:G[cu])if(pa!=to){dfs(to,cu);dp[cu][0]+=dp[to][0]+dp[to][1];f=true;dp[cu][0]%=mod;if(pa!=0&&cu!=0){dp[cu][1]+=dp[to][0]+dp[to][1];dp[cu][1]%=mod;}}if(!f){dp[cu][0]++;}if(cu!=0&&pa!=0){dp[cu][1]+=dp[cu][0];dp[cu][1]%=mod;}return ;}int main(void){cin >> N;ll ans=1;rep(i,1,N){int p;cin >> p;p--;G[p].push_back(i);G[i].push_back(p);if(p!=0){ans*=2;ans%=mod;}}cout << ans << endl;}