QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#575179 | #1882. Drunkards | liaojiqing2012 | WA | 15ms | 10612kb | Python3 | 1.1kb | 2024-09-19 11:08:36 | 2024-09-19 11:08:38 |
Judging History
answer
MOD = 998244353
def mod_inv(x, mod):
# 费马小定理计算逆元
return pow(x, mod - 2, mod)
def solve(n, p, a):
dp = [[0] * (2 * n + 1) for _ in range(n + 1)]
dp[0][n] = 1 # 初始在酒吧位置
prob_stay = p * pow(100, MOD-2, MOD) % MOD # 不动的概率
prob_move = (100 - p) * pow(100, MOD-2, MOD) % MOD # 移动的概率
for i in range(n):
for j in range(2 * n + 1):
if dp[i][j] != 0:
# 不动的情况
dp[i+1][j] = (dp[i+1][j] + dp[i][j] * prob_stay) % MOD
# 移动的情况
next_pos = j + a[i]
if 0 <= next_pos <= 2 * n:
dp[i+1][next_pos] = (dp[i+1][next_pos] + dp[i][j] * prob_move) % MOD
# 求所有房子的概率和
total_prob = sum(dp[n][j] for j in range(2 * n + 1)) % MOD
inv_denom = mod_inv(2 * n + 1, MOD) # (2n+1)的逆元
result = total_prob * inv_denom % MOD
return result
# 读取输入
n, p = map(int, input().split())
a = list(map(int, input().split()))
# 输出结果
print(solve(n, p, a))
详细
Test #1:
score: 0
Wrong Answer
time: 15ms
memory: 10612kb
input:
2 28 1 1
output:
598946612
result:
wrong answer 1st numbers differ - expected: '702764025', found: '598946612'