QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #456938 | #3228. Hyperrectangle | propane | AC ✓ | 230ms | 5304kb | C++20 | 1.3kb | 2024-06-28 18:13:55 | 2024-06-28 18:13:57 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
}
void sub(int &a, int b){
a -= b;
if (a < 0) a += mod;
}
int mul(int a, int b){
return 1LL * a * b % mod;
}
int dp[2][305 * 305], ndp[2][305 * 305];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
int s;
cin >> s;
dp[0][0] = 1;
for(auto x : a){
memset(ndp, 0, sizeof ndp);
for(int i = 0; i < 2; i++){
for(int j = 0; j <= s; j++){
add(ndp[i][j], dp[i][j]);
if (j + x <= s){
add(ndp[i ^ 1][j + x], dp[i][j]);
}
}
}
swap(dp, ndp);
}
int ans = 0;
for(int i = 0; i <= s; i++){
int t = 1;
for(int j = 0; j < n; j++) t = mul(t, s - i);
add(ans, mul(dp[0][i], t));
sub(ans, mul(dp[1][i], t));
}
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 65ms
memory: 5040kb
input:
300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
117608222
result:
ok single line: '117608222'
Test #2:
score: 0
Accepted
time: 129ms
memory: 4948kb
input:
300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
642790854
result:
ok single line: '642790854'
Test #3:
score: 0
Accepted
time: 83ms
memory: 5236kb
input:
300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
958840715
result:
ok single line: '958840715'
Test #4:
score: 0
Accepted
time: 40ms
memory: 5240kb
input:
300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 131ms
memory: 5012kb
input:
300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
78005621
result:
ok single line: '78005621'
Test #6:
score: 0
Accepted
time: 40ms
memory: 5068kb
input:
300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 ...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 103ms
memory: 5008kb
input:
300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 ...
output:
679611978
result:
ok single line: '679611978'
Test #8:
score: 0
Accepted
time: 230ms
memory: 5068kb
input:
300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 ...
output:
535199056
result:
ok single line: '535199056'
Test #9:
score: 0
Accepted
time: 90ms
memory: 5000kb
input:
300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 ...
output:
940580130
result:
ok single line: '940580130'
Test #10:
score: 0
Accepted
time: 81ms
memory: 5100kb
input:
300 25 196 113 207 102 81 272 39 245 105 188 47 123 160 81 54 246 163 252 141 257 202 87 90 228 193 18 80 294 168 158 272 245 293 272 211 54 154 248 274 163 73 107 104 54 42 167 208 13 189 32 202 126 13 294 228 46 177 195 294 163 60 107 116 55 90 291 97 280 7 197 8 12 101 232 243 220 279 38 148 222 ...
output:
231553137
result:
ok single line: '231553137'
Test #11:
score: 0
Accepted
time: 69ms
memory: 5300kb
input:
300 108 299 163 54 16 99 120 240 191 275 18 28 136 231 276 98 40 190 141 83 32 281 261 181 43 205 136 233 235 263 15 286 138 263 227 121 2 268 167 212 55 136 279 193 293 129 105 222 252 100 217 181 250 6 242 159 157 83 220 221 183 125 85 196 223 280 154 214 171 257 244 288 230 192 90 61 17 180 259 1...
output:
150442010
result:
ok single line: '150442010'
Test #12:
score: 0
Accepted
time: 48ms
memory: 5004kb
input:
300 251 67 279 154 80 47 90 165 5 59 116 242 141 101 88 282 173 118 58 24 10 14 197 69 110 268 172 218 112 201 14 254 94 259 263 158 80 129 159 51 28 190 258 176 41 103 204 239 89 162 36 46 293 99 158 223 145 196 66 178 122 222 61 51 206 212 113 114 220 24 83 221 47 59 54 110 29 131 242 171 297 76 2...
output:
248429428
result:
ok single line: '248429428'
Test #13:
score: 0
Accepted
time: 45ms
memory: 5296kb
input:
300 129 47 218 278 168 3 119 212 216 203 82 95 53 76 186 111 163 231 161 130 12 295 166 174 140 74 70 276 102 185 33 5 294 87 128 115 259 256 94 80 176 59 216 112 168 246 211 43 195 250 15 39 164 265 167 225 71 46 89 228 102 253 36 83 145 157 29 278 31 136 196 292 29 14 143 261 92 239 299 176 17 112...
output:
112867964
result:
ok single line: '112867964'
Test #14:
score: 0
Accepted
time: 41ms
memory: 5268kb
input:
300 260 216 165 237 133 262 12 173 21 155 236 192 274 211 114 6 230 56 123 41 242 31 252 183 277 268 166 16 144 299 265 255 162 246 11 159 83 240 139 180 135 117 255 256 221 246 197 68 205 275 7 215 136 69 256 6 152 3 84 108 291 50 100 210 175 147 221 231 176 74 79 180 103 50 192 91 151 181 236 223 ...
output:
993752865
result:
ok single line: '993752865'
Test #15:
score: 0
Accepted
time: 36ms
memory: 5236kb
input:
300 157 23 254 83 52 228 300 94 291 68 151 263 131 83 236 226 132 229 194 59 154 129 91 265 10 242 35 88 64 113 106 33 41 168 254 50 208 138 252 260 210 173 1 158 63 26 231 57 48 6 283 55 176 112 22 262 177 79 246 160 38 63 223 218 124 276 68 111 183 248 77 48 52 43 217 23 150 238 135 118 123 11 214...
output:
68532537
result:
ok single line: '68532537'
Test #16:
score: 0
Accepted
time: 40ms
memory: 5304kb
input:
300 122 212 29 246 136 104 4 248 181 18 44 111 279 254 18 242 113 135 221 141 85 280 223 226 95 268 132 184 77 175 128 260 131 261 219 290 242 152 124 15 215 24 40 230 182 19 74 232 68 179 162 177 52 232 236 30 111 137 36 279 165 262 137 116 149 172 199 154 241 185 231 265 233 55 123 81 22 158 288 1...
output:
982210912
result:
ok single line: '982210912'
Test #17:
score: 0
Accepted
time: 40ms
memory: 5004kb
input:
300 85 265 220 60 20 46 188 17 161 249 162 3 265 13 117 160 273 59 111 135 67 146 183 29 252 294 39 28 297 67 141 251 49 77 75 189 218 191 100 93 4 178 51 249 44 269 116 21 202 275 224 90 216 290 255 234 49 108 66 163 171 98 100 141 174 226 134 195 286 55 176 114 9 153 19 135 84 115 51 239 129 186 1...
output:
164617402
result:
ok single line: '164617402'
Test #18:
score: 0
Accepted
time: 40ms
memory: 5000kb
input:
300 227 203 245 287 130 168 113 265 61 49 143 261 264 157 103 295 87 193 287 177 220 56 96 29 272 85 78 12 296 277 109 162 166 51 112 2 186 121 10 29 97 230 205 3 54 4 44 135 141 81 295 70 157 199 259 240 292 13 296 51 19 166 185 173 240 255 167 207 145 206 40 230 84 23 199 40 34 15 26 129 178 12 58...
output:
980808741
result:
ok single line: '980808741'
Test #19:
score: 0
Accepted
time: 40ms
memory: 5012kb
input:
300 12 173 56 131 191 134 254 48 75 137 292 10 31 5 3 262 65 176 88 176 231 21 290 270 288 196 269 25 278 19 86 240 192 224 263 37 235 235 173 49 79 266 285 249 84 193 249 65 91 5 202 5 19 46 42 84 142 172 213 27 212 147 273 120 180 244 59 241 279 48 173 256 234 208 192 50 85 97 81 134 208 239 165 1...
output:
502256174
result:
ok single line: '502256174'
Test #20:
score: 0
Accepted
time: 33ms
memory: 5268kb
input:
248 66 294 178 278 70 186 201 237 214 70 189 181 120 245 56 287 128 147 202 51 226 277 139 222 128 93 288 132 162 271 128 200 259 288 165 209 95 219 14 240 16 156 91 186 47 287 274 161 274 195 262 276 229 1 136 9 255 156 284 36 155 192 234 186 277 145 211 136 57 39 258 55 52 253 269 200 47 243 232 1...
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 7ms
memory: 5004kb
input:
73 120 161 7 117 109 120 122 186 10 22 186 127 286 8 281 248 244 131 211 152 297 103 31 114 288 93 148 253 235 215 54 181 117 44 188 264 68 3 108 146 18 138 136 177 224 56 93 55 231 69 203 298 196 74 294 275 286 156 116 258 141 91 154 9 110 13 142 18 106 46 136 92 172 1
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 15ms
memory: 5004kb
input:
109 174 134 260 226 216 114 292 37 100 255 190 210 19 70 126 294 206 159 84 176 40 199 146 258 291 137 62 233 136 107 100 63 105 19 133 228 77 181 115 112 296 101 182 204 100 203 106 138 244 192 13 219 174 35 263 64 110 255 150 264 275 125 41 25 155 32 163 152 68 235 183 96 170 198 46 292 289 279 50...
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 6ms
memory: 5068kb
input:
91 193 289 5 177 191 105 187 108 205 232 57 45 70 198 192 267 79 123 137 96 17 241 34 72 86 271 69 194 180 146 129 292 174 204 225 213 267 166 70 152 111 167 54 203 54 257 193 10 298 208 84 15 86 152 211 254 256 277 146 288 176 26 264 58 215 141 108 164 93 223 237 168 136 253 43 38 79 147 198 26 271...
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 23ms
memory: 5064kb
input:
194 154 3 128 231 204 223 225 28 189 35 208 29 77 27 237 54 67 166 243 57 164 35 148 133 6 251 43 176 26 222 271 38 35 285 199 28 159 26 254 181 299 1 50 281 204 295 74 86 218 38 293 185 257 185 261 71 152 143 27 138 156 57 300 167 128 207 83 19 259 65 95 172 127 79 240 22 218 194 78 156 244 162 71 ...
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 8ms
memory: 5108kb
input:
57 185 75 112 151 93 97 162 195 78 291 104 153 108 12 62 161 160 197 233 13 177 125 215 146 123 221 72 46 45 262 120 277 279 167 165 118 114 245 51 8 85 165 288 91 199 78 43 91 138 189 66 21 287 278 66 22 249 0
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 22ms
memory: 5060kb
input:
186 157 189 9 91 186 148 279 98 66 86 125 217 215 178 174 208 63 1 247 269 50 258 217 236 46 116 200 266 96 97 147 133 18 159 268 203 252 163 267 20 152 132 152 231 296 274 107 9 201 65 172 99 79 152 41 206 141 216 176 259 107 257 296 30 268 245 239 136 224 121 23 31 276 97 230 206 34 65 71 75 88 75...
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 31ms
memory: 5076kb
input:
259 1 132 258 42 230 4 22 182 283 259 169 4 267 243 189 172 15 281 29 236 221 128 19 85 84 281 81 167 8 250 199 267 157 212 29 215 272 107 207 237 215 30 174 41 119 77 74 142 145 17 299 137 152 8 86 115 227 211 223 117 69 249 49 292 70 299 103 268 92 36 151 278 112 216 279 28 97 270 138 17 141 219 2...
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 19ms
memory: 5064kb
input:
169 69 174 250 160 177 126 199 20 177 205 226 247 56 194 209 168 252 238 72 159 277 126 105 255 159 69 28 271 138 253 182 298 121 204 55 44 121 233 58 260 124 150 189 298 237 85 215 188 300 42 252 39 272 196 32 128 227 185 13 101 138 80 120 135 135 2 173 55 203 191 205 27 222 148 237 259 292 44 106 ...
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 29ms
memory: 5064kb
input:
215 88 238 71 77 282 38 60 91 178 24 274 67 39 163 55 233 122 108 257 3 80 233 124 285 73 120 240 113 245 271 217 114 79 163 25 34 234 211 226 141 178 300 42 141 185 120 57 102 56 49 127 149 213 204 216 162 44 116 36 259 36 110 225 129 284 20 142 80 20 120 196 252 195 75 63 292 204 285 258 35 56 145...
output:
0
result:
ok single line: '0'
Test #30:
score: 0
Accepted
time: 1ms
memory: 5068kb
input:
2 173 66 0
output:
0
result:
ok single line: '0'
Test #31:
score: 0
Accepted
time: 1ms
memory: 5064kb
input:
2 81 93 0
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 1ms
memory: 5008kb
input:
2 6 3 4
output:
15
result:
ok single line: '15'
Test #33:
score: 0
Accepted
time: 2ms
memory: 4956kb
input:
5 12 34 56 78 90 123
output:
433127538
result:
ok single line: '433127538'