QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#575179#1882. Drunkardsliaojiqing2012WA 15ms10612kbPython31.1kb2024-09-19 11:08:362024-09-19 11:08:38

Judging History

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

  • [2024-09-19 11:08:38]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:10612kb
  • [2024-09-19 11:08:36]
  • 提交

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'