求助,为啥要乘以(n+2)/2?
查看原帖
求助,为啥要乘以(n+2)/2?
1122530
elpsconr楼主2024/8/9 00:57

为啥求完其他点的期望后还要乘以(n+2)/2?其他点概率为(1-dp[k])/(n-1),再乘以(n-1)即为期望,后面为啥又有加乘以(n+2)/2的行为,求解

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
const int N=3e5+6,yyx=998244353;
int n,k,dp[N];
int mul(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=(res*x)%yyx;
        y>>=1;
        x=(x*x)%yyx;
    }
    return res;
}
void solve(){
  cin>>n>>k;
  int q=2*(n-1)%yyx*mul(n*n%yyx,yyx-2)%yyx;//从最左边到其他球
  int p=2*mul(n*n%yyx,yyx-2)%yyx;//从其他点到最左边
  dp[0]=1;
  for(int i=1;i<=k;++i){
    dp[i]=((p%yyx*(1-dp[i-1]+yyx)%yyx+(((1-q)%yyx+yyx)%yyx)*(dp[i-1])%yyx)%yyx+yyx)%yyx;//dp[i]为让黑球保持在最左边的概率
  }
  int ans=(1-dp[k]+yyx)%yyx*mul(n-1,yyx-2)%yyx;
  ans=(ans%yyx*(n-1)%yyx*(n+2)%yyx*mul(2,yyx-2)%yyx+yyx)%yyx;
  //ans=(ans%yyx*(n-1)%yyx+yyx)%yyx;//不多乘以(n+2)/2ac不了
  cout<<((dp[k]+ans)%yyx+yyx)%yyx<<endl;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int _=1;
    //cin>>_;
    while(_--)
    solve();
    return 0;
}
2024/8/9 00:57
加载中...