门芯袜子求助O(nm)dp为什么WA了!?!?!?!??!?!?!?!?!?!
查看原帖
门芯袜子求助O(nm)dp为什么WA了!?!?!?!??!?!?!?!?!?!
891956
TempestMiku楼主2023/8/25 17:42

dpi,jdp_{i,j}表示剩下 ii 个yes,jj 个 no。

如果yes比no多肯定选yes,然后分为答案恰好是yes和no的情况,分别从 dpi−1,jdp_{i-1,j} 和 dpi,j−1dp_{i,j-1}转移过来,11是权值。

同理no比yes多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
    inline int read(){
        int f(1),x(0);
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    inline void Write(int x){
        if(x>9) Write(x/10);
        putchar(x%10+48);
    }
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        Write(x);
        putchar('\n');
    }
}
using namespace Testify;
int n,m,Tempestissimo(0);
const int mod=998244353;
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
inline int niyuan(int x){
    return qpow(x,mod-2)%mod;
}
int dp[5005][5005];//剩下i个yes,j个no时期望对多少题
signed main(void){
    n=read(),m=read();
    dp[0][0]=0;
    dp[1][0]=dp[0][1]=1;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m;j++){
            if(i>=j){
                dp[i][j]=((i*niyuan(i+j)%mod*(1+dp[i-1][j]))%mod+(j*niyuan(i+j))%mod*(0+dp[i][j-1])%mod)%mod;
            }
            else{
                dp[i][j]=((j*niyuan(i+j)%mod*(1+dp[i][j-1]))%mod+(i*niyuan(i+j))%mod*(0+dp[i-1][j])%mod)%mod;
            }
        }
    }
    write(dp[n][m]%mod);
    return 0;
}

求助!!!!!

2023/8/25 17:42
加载中...