因为最后答案要写成分数形式p/q.发现q每次都增大2.
dp[i]=(1-dp[i-1])/2 = (1+dp[i-2])/4 =(2^0+2^2+dp[i-4])/2^4).. 当i为odd时,dp[1]=0时终止,分子为公比为2^2的等比序列的前n-1/2项.
p=((2^2)^(n-1/2)-1)/2^2-1=(2^(n-1)-1)/3. 偶数类似 用快速幂计算公式即可.ps:分子为Jacobsthal number
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; const ll mod=1e9+7; ll k,a[N]; ll powmod(ll x,ll n) { ll s=1; while(n) { if(n&1) s=(s*x)%mod; n>>=1,x=(x*x)%mod; } return s; } int main() { while(cin>>k) { ll n=2; ll flag=-1; for(int i=1;i<=k;i++) { scanf("%I64d",&a[i]); n=powmod(n,a[i]); if(a[i]%2==0) flag=1; } ll q=n*powmod(2ll,mod-2)%mod;//2^(n-1) ll p=((q+flag+mod)%mod*powmod(3ll,mod-2)%mod)%mod; cout<<p<<'/'<<q<<endl; } return 0; }
P.D
题意:1为根结点的树,从u到u的任意一个子树v的概率都相同,相邻结点花费时间为1. n<=1e5,从1出发,问到达每个结点的期望时间? 设f[u]:到达u的期望时间,每次都是从fa遍历若干个u的兄弟子树,然后达到u. 按照样例,到达2的可能性有,(245),(254),(425),(524),(452),(542).有p个兄弟就,有p!种可能 f[u]=f[fa]+ (sum[所有遍历序列中在u之前兄弟的size累加和]+p!(u自己))/p! sum:u的任意一个兄弟v在p!排列中要么在u之前要么在u之后,只有这两种可能&&这两个事件概率相同. 每个兄弟v贡献p!/2 sum=p!/2 * (sz[fa]-sz[u])
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; vector<int> e[N]; int n,sz[N]; double f[N]; void dfs(int u,int fa) { sz[u]=1; for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(fa==v) continue; dfs(v,u); sz[u]+=sz[v]; } } void dfs1(int u,int fa) { if(fa==-1) f[u]=1.0; else f[u]=f[fa]+1.0*(sz[fa]-sz[u]-1)/2.0+1; for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(fa==v) continue; dfs1(v,u); } } int main() { while(cin>>n) { int u,v; for(int i=2;i<=n;i++) { scanf("%d",&u); e[u].push_back(i); e[i].push_back(u); } dfs(1,-1); dfs1(1,-1); for(int i=1;i<=n;i++) printf("%.6lf%c",f[i],i==n?'\n':' '),e[i].clear(); } return 0; }