QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #489615 | #8815. Space Station | daishuchen2010 | WA | 199ms | 8064kb | C++20 | 1.1kb | 2024-07-24 21:53:16 | 2024-07-24 21:53:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 5,mod = 998244353;
int C[MAXN][MAXN],dp[MAXN][MAXN * MAXN];
inline long long fast_pow(long long a,int b = mod - 2)
{
long long ans = 1;
for (; b > 0; b >>= 1,a *= a,a %= mod) if (b & 1) ans *= a,ans %= mod;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,sum = 0,x;
cin >> n >> m;
C[0][0] = dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
for (int i = 1; i <= n; i++)
{
cin >> x;
sum += x;
for (int j = i; j >= 1; j--)
{
for (int k = sum; k >= x; k--)
{
dp[j][k] += dp[j - 1][k - x];
dp[j][k] %= mod;
}
}
}
int ans = 0,tmp;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
{
if (1.0 * j / i < m) tmp = 1ll * j * fast_pow(i) % mod;
else tmp = m;
ans += 1ll * tmp * dp[i][j] % mod * fast_pow(C[n][i]) % mod;
ans %= mod;
}
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3596kb
input:
3 3 2 3 4
output:
499122185
result:
ok 1 number(s): "499122185"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
5 5 24 41 29 6 40
output:
25
result:
ok 1 number(s): "25"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
10 34 91 86 1 14 98 13 85 64 91 20
output:
707882334
result:
ok 1 number(s): "707882334"
Test #6:
score: 0
Accepted
time: 146ms
memory: 7720kb
input:
100 9 83 99 170 80 174 137 1 91 111 35 69 39 148 76 142 90 105 30 114 176 196 85 26 109 162 167 171 148 169 162 159 3 4 6 33 61 163 7 77 63 8 20 13 51 26 11 149 136 134 187 96 95 113 104 128 48 167 74 18 91 200 62 167 32 5 180 189 39 63 111 68 72 81 128 42 13 57 180 111 91 83 177 34 45 158 29 114 33...
output:
82380556
result:
ok 1 number(s): "82380556"
Test #7:
score: 0
Accepted
time: 175ms
memory: 8064kb
input:
100 33 24 157 144 142 151 8 93 54 189 74 12 129 77 95 59 13 159 48 67 116 174 194 9 166 170 84 136 68 39 181 133 190 37 115 42 95 134 148 91 59 130 1 68 48 14 126 193 50 192 196 44 85 37 96 66 39 180 129 22 2 17 101 45 159 171 68 113 142 197 156 63 96 185 108 72 69 144 33 115 142 139 11 57 76 126 19...
output:
516465986
result:
ok 1 number(s): "516465986"
Test #8:
score: 0
Accepted
time: 183ms
memory: 8016kb
input:
100 61 68 6 125 92 128 192 177 10 171 26 52 123 118 123 176 39 13 171 108 169 160 199 81 127 83 106 93 181 118 103 4 90 173 128 146 24 9 186 2 56 45 182 26 36 97 34 29 76 59 22 95 74 162 192 101 29 1 176 34 10 26 140 27 190 128 157 37 141 131 113 49 111 96 183 6 125 31 86 23 96 195 38 81 19 190 164 ...
output:
272517095
result:
ok 1 number(s): "272517095"
Test #9:
score: 0
Accepted
time: 199ms
memory: 8044kb
input:
100 81 17 160 3 145 193 71 69 165 58 161 196 14 48 134 93 154 67 93 148 117 138 109 64 88 99 127 146 101 84 129 82 181 5 133 50 154 83 24 105 149 55 67 73 25 77 149 73 190 118 136 147 55 86 88 135 116 22 127 143 121 43 75 1 21 189 30 160 132 161 157 35 30 112 58 133 85 14 35 139 43 43 168 105 154 61...
output:
595123712
result:
ok 1 number(s): "595123712"
Test #10:
score: 0
Accepted
time: 163ms
memory: 7912kb
input:
100 9 165 10 72 7 74 150 153 25 136 105 147 112 193 161 10 180 26 111 101 66 115 26 143 145 107 44 111 14 154 147 152 168 38 41 154 76 150 61 23 154 178 160 127 22 65 57 117 8 185 146 191 52 2 184 73 107 147 86 147 24 148 11 183 156 155 119 180 131 95 106 118 45 24 126 67 142 197 88 47 197 100 194 3...
output:
691953469
result:
ok 1 number(s): "691953469"
Test #11:
score: 0
Accepted
time: 158ms
memory: 7660kb
input:
100 33 9 163 54 60 146 37 45 180 118 145 91 106 122 172 127 95 80 129 46 6 101 135 126 2 116 169 172 134 25 77 31 67 70 150 58 5 25 99 30 46 188 37 85 10 140 69 153 26 43 163 147 137 135 176 116 90 168 133 159 136 165 146 69 180 16 104 8 122 29 159 8 60 127 9 1 94 92 141 51 48 52 21 49 128 93 72 146...
output:
431283290
result:
ok 1 number(s): "431283290"
Test #12:
score: 0
Accepted
time: 194ms
memory: 7972kb
input:
100 57 150 109 132 122 115 13 33 136 4 184 131 92 155 95 140 17 38 43 191 59 79 44 110 163 36 190 25 142 95 191 101 54 6 51 58 39 196 40 149 139 111 122 44 199 128 80 197 140 6 77 95 31 51 168 54 177 189 84 67 143 182 185 146 107 173 89 131 121 163 108 90 83 143 84 31 150 75 186 167 195 12 55 73 62 ...
output:
643516605
result:
ok 1 number(s): "643516605"
Test #13:
score: 0
Accepted
time: 182ms
memory: 7640kb
input:
100 82 194 63 113 71 92 196 117 3 83 128 74 183 93 10 58 36 92 165 40 7 57 50 85 20 44 107 86 55 61 17 76 145 39 64 67 169 71 78 155 40 121 7 98 100 11 100 40 166 169 191 42 116 183 168 88 167 10 131 72 54 88 24 24 42 138 170 151 120 1 161 85 98 55 160 70 6 162 143 75 45 68 82 200 101 37 104 39 72 1...
output:
231671459
result:
ok 1 number(s): "231671459"
Test #14:
score: -100
Wrong Answer
time: 172ms
memory: 7908kb
input:
100 10 38 120 191 29 165 171 9 159 65 167 114 177 126 133 175 158 51 87 184 148 42 71 68 77 156 129 147 175 27 44 50 36 175 76 67 99 146 115 162 133 36 196 57 88 199 111 180 80 123 112 94 105 100 168 123 158 135 90 84 158 9 55 6 73 104 155 179 111 127 109 71 113 167 131 100 166 144 100 191 200 12 11...
output:
751202377
result:
wrong answer 1st numbers differ - expected: '602660662', found: '751202377'