fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll          long long int
  3. #define pb          emplace_back
  4. #define mp          make_pair
  5. #define pii         pair<int,int>
  6. #define vi          vector<int>
  7. #define Max(a,b)    ((a)>(b)?(a):(b))
  8. #define Min(a,b)    ((a)<(b)?(a):(b))
  9. #define rep(i,a,b)  for (__typeof((b)) i=(a);i<(b);i+=1)
  10. #define all(a)      (a).begin(),(a).end()
  11. #define F           first
  12. #define S           second
  13. #define sz(x)       (int)x.size()
  14. #define hell        1000000007
  15. #define endl        '\n'
  16. #define debug(a)    cerr<<#a<<": ";for(auto i:a)cerr<<i<<" ";cerr<<'\n';
  17. using namespace std;
  18. vector<vi>m;
  19. vi visited;
  20. vi ans;
  21. vi cnt;
  22. ll fact[1000000];
  23. vi x;
  24. vi temp;
  25. ll expo(ll base, ll exponent, ll mod) {								//return base^exponent modulo modulus
  26. 	ll res = 1;
  27. 	while(exponent !=0 ) {
  28. 		if((exponent&1) == 1) {
  29. 			res= res*base ;
  30. 			res = res%mod;
  31. 		}
  32. 		base = base*base;
  33. 		base %= mod;
  34. 		exponent>>= 1;
  35. 	}
  36. 	return res;
  37. }
  38. void dfs2(int u){
  39.     if(sz(m[u])==0){
  40.         cnt[u]=0;
  41.         return;
  42.     }
  43.     ll cur=0;
  44.     for(auto i:m[u]){
  45.         dfs2(i);
  46.         cur+=cnt[i]+1;
  47.     }
  48.     cnt[u]=cur;
  49. }
  50. void dfs(int u){
  51.     visited[u]=1;
  52.     if(sz(m[u])==0){
  53.         ans[u]=1;
  54.         return;
  55.     }
  56.     for(auto i:m[u]){
  57.         dfs(i);
  58.     }
  59.     ll cur=1;
  60.     for(auto i:m[u]){
  61.         cur=(cur*ans[i])%hell;
  62.     }
  63.     ll num=fact[cnt[u]];
  64.     ll den=1;
  65.     for(auto i:m[u]){
  66.         den=(den*fact[cnt[i]+1])%hell;
  67.     }
  68.     ans[u]=(((cur*num)%hell)*expo(den,hell-2,hell))%hell;
  69. }
  70. int n;
  71. void filltemp(int parent,int next){
  72.     int start=parent+1;
  73.     if(start>=next)return;
  74.     int i;
  75.     for(i=start;x[i]+i+1<next;i=x[i]+i+1){
  76.         temp[i]=i+x[i]+1;
  77.         filltemp(i,temp[i]);
  78.     }
  79.     temp[i]=parent;
  80.     if(temp[i]==-1)temp[i]=n;
  81.     filltemp(i,next);
  82. }
  83. void solve(){
  84.     m.clear();
  85.     ans.clear();
  86.     cnt.clear();
  87.     visited.clear();
  88.     x.clear();
  89.     temp.clear();
  90.     cin>>n;
  91.     x.resize(n);
  92.     temp.resize(n+1);
  93.     m.resize(n+1);
  94.     ans.resize(n+1);
  95.     cnt.resize(n+1);
  96.     visited.resize(n+1);
  97.     rep(i,0,n){
  98.         cin>>x[i];
  99.     }
  100.     rep(i,0,n){
  101.         if(i+x[i]>n-1){
  102.             cout<<0<<endl;
  103.             return;
  104.         }
  105.     }
  106.     filltemp(-1,n);
  107.     assert(count(all(temp),n)==1);
  108.     rep(i,0,n){
  109.         m[temp[i]].pb(i);
  110.     }
  111.     dfs2(n);
  112.     dfs(n);
  113.     if(find(all(visited),0)==visited.end())cout<<ans[n]<<endl;
  114.     else cout<<0<<endl;
  115. }
  116.  
  117. int main(){
  118. 	ios_base::sync_with_stdio(false);
  119. 	cin.tie(0);
  120. 	cout.tie(0);
  121.     fact[0]=1;
  122.     rep(i,1,1000000)fact[i]=(fact[i-1]*i)%hell;
  123. 	int t=1;
  124. 	cin>>t;
  125. 	while(t--){
  126. 		solve();
  127. 	}
  128. 	return 0;
  129. }
  130.  
Success #stdin #stdout 0.01s 11288KB
comments (?)
stdin
copy 
3
4
0 2 1 0
4
0 2 1 1
3
2 1 0
stdout
copy 
3
0
1
https://ideone.com/u9Av7q
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!