QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#396666#1882. DrunkardsdeepthoughtML 0ms3972kbC++233.0kb2024-04-22 23:26:522024-04-22 23:26:52

Judging History

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

  • [2024-04-22 23:26:52]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3972kb
  • [2024-04-22 23:26:52]
  • 提交

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 dp[2 * n + 1][2 * n + 1][2 * n + 1];
    for(int i = 0; i < 2 * n + 1; i++){
        for(int j = 0; j < 2 * n + 1; j++) {
            for(int k = 0; k < 2 * n + 1; k++) {
                dp[i][j][k] = 0;
            }
        }
        dp[i][n][0] = home_prob;
    }
    // dp[home][idx][time]

    mint answer = home_prob; // if home = n

    dp[n][n][0] = 0;


    for(int time = 1; time <= n; time++) {
        for(int home = 0; home <= 2 * n; home++) {
            for(int idx = 0; idx <= 2 * n; idx++) {
                dp[home][idx][time] += dp[home][idx][time - 1] * stay;
                if(idx > 0) {
                    if(arr[time] == 1) {
                        dp[home][idx][time] += dp[home][idx - 1][time - 1] * move;
                    }
                }
                if(idx < 2 * n) {
                    if(arr[time] == -1) {
                        dp[home][idx][time] += dp[home][idx + 1][time - 1] * move;
                    }
                }
                if(home == idx) {
                    // cout << idx << " " << dp[home][idx][time] << endl;
                    answer += dp[home][idx][time];
                    // if(home == 6 and idx == 6 and time == 2) cout << dp[home][idx][time] << endl;
                    // if(dp[home][idx][time] != 0) cout << dp[home][idx][time] << " home:" << home << " time:" << time << endl;
                    dp[home][idx][time] = 0;
                }
            }
        } 
    }

    cout << ((int)answer) << endl;
    // cout << home_prob << endl;
    // cout << "prob:" << (home_prob * stay * stay * move) << endl;
}

/*

d.in: 340310575

a.in: 702764025

*/



詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

5 50
-1 1 -1 -1 -1

output:

17015529

result:

ok 1 number(s): "17015529"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

5 50
-1 1 -1 1 1

output:

680621150

result:

ok 1 number(s): "680621150"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

10 50
1 1 1 1 1 -1 -1 -1 1 1

output:

812744705

result:

ok 1 number(s): "812744705"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

10 50
-1 -1 1 1 -1 -1 1 -1 -1 -1

output:

158575275

result:

ok 1 number(s): "158575275"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

15 65
1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 1

output:

553313087

result:

ok 1 number(s): "553313087"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

15 65
-1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1

output:

140408188

result:

ok 1 number(s): "140408188"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

10 7
1 1 1 1 1 1 1 1 1 1

output:

375530019

result:

ok 1 number(s): "375530019"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

10 73
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

289966217

result:

ok 1 number(s): "289966217"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10 0
1 1 -1 1 1 1 -1 1 -1 1

output:

95070891

result:

ok 1 number(s): "95070891"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10 0
1 1 1 -1 1 1 1 1 1 1

output:

570425345

result:

ok 1 number(s): "570425345"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

10 0
-1 1 1 1 -1 1 -1 -1 1 1

output:

475354454

result:

ok 1 number(s): "475354454"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

10 0
-1 -1 -1 -1 -1 -1 1 -1 1 -1

output:

332748118

result:

ok 1 number(s): "332748118"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 0
1 1 1 1 1 1 -1 1 1 1

output:

570425345

result:

ok 1 number(s): "570425345"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10 0
-1 -1 -1 1 1 1 -1 1 -1 1

output:

475354454

result:

ok 1 number(s): "475354454"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 0
-1 1 1 1 1 -1 -1 1 -1 1

output:

95070891

result:

ok 1 number(s): "95070891"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 100
-1 1 -1 1 1 -1 -1 -1 -1 -1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10 100
1 1 1 1 1 1 -1 1 1 1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #19:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

10 100
-1 -1 -1 -1 1 1 -1 -1 1 1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

10 27
1 -1 -1 1 -1 -1 1 -1 -1 1

output:

89502877

result:

ok 1 number(s): "89502877"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

10 27
1 1 -1 1 -1 1 1 -1 -1 1

output:

602378374

result:

ok 1 number(s): "602378374"

Test #22:

score: -100
Memory Limit Exceeded

input:

5000 25
1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 -1 -1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 ...

output:


result: