QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398061#1882. DrunkardsdeepthoughtWA 1ms3600kbC++232.7kb2024-04-24 21:41:352024-04-24 21:41:35

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 21:41:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3600kb
  • [2024-04-24 21:41:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template <int MOD> struct modint{
	static const int mod = MOD;
	int v;
	operator int() const {return v;} 
	modint():v(0) {}
	modint(long long _v):v(int(_v%MOD)) {v += (v<0)*MOD;}
	modint& operator+=(modint o) {if((v += o.v) >= MOD) v-= MOD; return *this;}
	modint& operator-=(modint o) {if((v -= o.v) < 0) v+= MOD; return *this;}
	modint& operator*=(modint o) {v = int((long long)v*o.v%MOD); return *this;}
	modint& operator/=(modint o) {return *this *= inv(o);}
	friend modint pow(modint a, long long p) {
		modint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }	friend modint inv(modint a) {assert(a.v != 0); return pow(a, MOD-2);}
	friend modint operator+(modint a, modint b) {return a += b;}
	friend modint operator-(modint a, modint b) {return a -= b;}
	friend modint operator*(modint a, modint b) {return a *= b;}
	friend modint operator/(modint a, modint b) {return a /= b;}
};
using mint = modint<(int)998244353>;

int main() {
    
    int n, pp;
    cin >> n >> pp;
    mint stay = (mint)pp * inv((mint)100);
    mint move = (mint)(100 - pp) * inv((mint)100);
    
    vector <int> arr(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    mint home_prob = inv(mint(2 * n + 1));
    mint leave_prob = home_prob * (mint)(2 * n);

    mint dp[2 * n + 1][2 * n + 1];

    for(int i = 0; i < 2 * n + 1; i++){
        for(int j = 0; j < 2 * n + 1; j++) {
            dp[i][j] = 0;
        }
    }

    // dp[time][distance]
    // you reach there at least once
    dp[0][n] = (mint) 1; // distance n - n = 0, can go + (n-n)


    for(int time = 1; time <= n; time++) {
        
        for(int distance = 0; distance <= 2 * n; distance++) {
 
            dp[time][distance] = dp[time - 1][distance] * stay;
            
            if(distance > 0) {
                if(arr[time] == 1) {
                    dp[time][distance] += dp[time - 1][distance - 1] * move; 
                }
            }
            
            if(distance < 2 * n) {
                if(arr[time] == -1) {
                    dp[time][distance] += dp[time - 1][distance + 1] * move;
                }
            }
        }
        // dp[time][n] = (mint) 1;

    }

    mint answer = (mint) 0;
    for(int i = 0; i <= 2 * n; i++) {
        answer += dp[n][i];
    }
    answer *= home_prob;
    // cout << (dp[2][3]) << endl;

    // cout << (move * stay * (mint) 2 + move*move) << endl;

//   _ _ N _ _

    cout << answer << endl;





}

/*

d.in: 340310575

a.in: 702764025







_ _ _ N _ _ _




*/



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3600kb

input:

2 28
1 1

output:

598946612

result:

wrong answer 1st numbers differ - expected: '702764025', found: '598946612'