VJ地址

題目大意： 有n個節點 從0-（n-1），連邊的規律為
即i點的父親只能是比i小的數，而且是隨機的，現在隨機選擇應該一個節點作為根，求這子樹的和的期望是多少。
思路：可以知道總共有（n-1）！顆樹，而且n個節點，每個節點選擇的概率是一樣的；所有期望值為：
所有樹的子樹權值和/（n）！；
那么所有樹的子樹權值和為多少呢？當畫出n=3.n=4的樹時，就會發現
g(0)=f(n-1);
g(1)=f(n-1)+f(n-1)/1;
g(i)=f(n-1)+f(n-1)/1+f(n-1)/2…+f(n-1)/i;

代碼：

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se secondusing namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=998244353; const ll N =1e5+10; const double eps = 1e-4; //const double pi=acos(-1); ll gcd(int a,int b){return !b?a:gcd(b,a%b);} ll qk(ll x,ll y){ll ans=1;while(y){if(y&1) ans=ans*x%mod;y>>=1;x=x*x%mod;}return ans; } ll n; ll dp[N]; ll a[N]; ll f[N]; int main() {int _;scanf("%d",&_);f[0]=1;for(int i=1;i<=1e5;i++) f[i]=(f[i-1]*i)%mod;while (_--){scanf("%lld",&n);for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);ll ans=a[1]*f[n-1];dp[1]=f[n-1];for(ll i=2;i<=n;i++){dp[i]=(dp[i-1]+f[n-1]*qk(i-1,mod-2)%mod)%mod;ans=(ans+a[i]*dp[i]%mod)%mod;}printf("%lld\n",ans*qk(f[n],mod-2)%mod);}return 0; }

總結

以上是生活随笔為你收集整理的HDU - 6267 （概论/找规律/递推）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。