QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#615609#1882. DrunkardsyaoyanfengWA 0ms3932kbC++14915b2024-10-05 19:29:492024-10-05 19:29:49

Judging History

This is the latest submission verdict.

  • [2024-10-05 19:29:49]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3932kb
  • [2024-10-05 19:29:49]
  • Submitted

answer

/*
倒序即可,fk
如果正序来做,那么无法得知转移到的位置是否之前走过
逆序做的话,影响的位置只有0,/fk
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5050, mod = 1e9 + 7;
int n, p, q;
int a[N];
int f[N][N << 1];
int qow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return ans;
}
signed main() {
    scanf("%lld%lld", &n, &p), p = p * qow(100, mod - 2) % mod, q = (mod + 1 - p) % mod;
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
    f[n + 1][n] = 1;
    for (int i = n; i >= 1; f[i][n] = 1, --i)
        for (int j = 0; j <= 2 * n; ++j)
            f[i][j] = (f[i + 1][j] * p + (j - a[i] >= 0 ? f[i + 1][j - a[i]] * q : 0)) % mod;
    for (int j = 0; j <= 2 * n; ++j) printf("%lld ", f[1][j]);
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3932kb

input:

2 28
1 1

output:

0 0 1 11200001 68800001 

result:

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