QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#615609 | #1882. Drunkards | yaoyanfeng | WA | 0ms | 3932kb | C++14 | 915b | 2024-10-05 19:29:49 | 2024-10-05 19:29:49 |
Judging History
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'