0分代码求调

大佬们好，本蒟蒻和题解的思路差不多，概率期望DP，比赛的时候过样例了，结果只A了两个点，爆零了，检查了long long和取模，应该没啥问题``` #include<bits/stdc++.h> using namespace std; #define ll long long const int mn=5000,p=998244353;

int n,Q;//,l[mn+3],r[mn+3]; ll Pow(ll a,ll b) { a%=p; ll ans=1%p; while(b>0) { if(b&1) ans=ansa%p; a=aa%p; b>>=1; } return ans; } ll rev[mn+3]; ll dp[mn+3][mn+3],Sdp[mn+3][mn+3]; //i是j祖先的概率和前缀和 ll ans[mn+3];

int main() { #ifndef ONLINE_JUDGE freopen("Tree.in","r",stdin); #endif cin>>n; //for(int i=2;i<=n;i++) // scanf("%d%d",l+i,r+i); for(int i=1;i<=n;i++) rev[i]=Pow(i,p-2);

CPP

for(int i=1;i<=n;i++) dp[i][i]=Sdp[i][i]=1;
for(int i=2;i<=n;i++) {
    int l,r;
    scanf("%d%d",&l,&r);
    for(int u=1;u<i;u++) {
        //u是l到r祖先的概率加起来
        dp[u][i]=(Sdp[u][r]-Sdp[u][l-1])
                 *rev[r-l+1]%p;
        Sdp[u][i]=(Sdp[u][i-1]+dp[u][i])%p;
    }
}
//cout<<dp[2][3];

cin>>Q;
while(Q--) {
    int u,v,val;
    scanf("%d%d%d",&u,&v,&val);
    if(u>v) swap(u,v);
    for(int i=1;i<=u;i++) {
        ll P=dp[i][v]-dp[i][u]*dp[u][v]%p;

//dp[i][v]=u为v祖先且i为v祖先的概率（此时等价于i为u祖先）

//+u不为v祖先且i为v祖先的概率

CPP

        ans[i]+=(dp[i][u]+dp[i][v]-
                 2*dp[i][u]*((dp[u][v]+P)%p)%p)
                *val%p;//容斥
        ans[i]%=p;
    }
    for(int i=u+1;i<=v;i++) 
        ans[i]+=dp[i][v]*val%p,ans[i]%=p;
}
for(int i=2;i<=n;i++) cout<<(ans[i]%p+p)%p<<" ";
return 0;

}

CPP

讨论操作

回复

相关推荐

0分代码求调