QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #124416 | #6669. Mapa | Hanx16Msgr | 0 | 12ms | 3468kb | C++14 | 1.2kb | 2023-07-14 18:55:25 | 2023-07-14 18:55:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7, _N = 100 + 5;
int T, n, m, len;
int Qpow(int x, int y) {
int res = 1, base = x;
for (; y; y >>= 1, base = 1ll * base * base % mod)
if (y & 1) res = 1ll * res * base % mod;
return res;
}
#define Inv(_) Qpow(_, mod - 2)
int x[_N], y[_N];
int Lang(int z) {
int res = 0;
for (int i = 1; i <= n; ++i) {
int s1 = 1, s2 = 1;
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
s1 = 1ll * s1 * (z - x[j]) % mod;
s2 = 1ll * s2 * (x[i] - x[j]) % mod;
}
(res += 1ll * y[i] * s1 % mod * Inv(s2) % mod) %= mod;
}
return res;
}
signed main() {
ios::sync_with_stdio(0); cout.tie(0);
cin >> T >> n;
if (T == 1) {
for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
cout << n * 30 << '\n';
for (int i = 1; i <= n; ++i) {
int val = Lang(i);
for (int y = 29; y >= 0; --y)
cout << ((val >> y) & 1);
}
} else {
cin >> m >> n;
string st; cin >> st;
n /= 30;
int p = 0;
for (int i = 1; i <= n; ++i) {
int val = 0;
for (int j = 29; ~j; --j, ++p)
if (st[p] == '1') val += 1 << j;
x[i] = i, y[i] = val;
}
for (int i = 1, x; i <= m; ++i) {
cin >> x;
cout << Lang(x) << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 12ms = 7ms + 5ms
memory: 3444kb,3468kb
input:
1 100 495528311 963488152 269613430 443544124 700489871 792354118 151890319 506569919 180452297 13229948 684464994 543841485 978085128 903812192 238355172 441140842 28061035 783291471 530823766 718942732 936853023 439421263 201361623 226633955 304644844 778868118 864860135 461524170 88300500 6959354...
output:
3000 0101110111100010001000001000001001011101111111010101100111011011001100100000110011110111100000011100011101000001000110110100011111000101100101100101001000101010100001010111101100101001100111111100101000000100001111001111100000111000111111100101111101011101100010001111111010110101101101111111111...
input:
2 100 79 3000 0101110111100010001000001000001001011101111111010101100111011011001100100000110011110111100000011100011101000001000110110100011111000101100101100101001000101010100001010111101100101001100111111100101000000100001111001111100000111000111111100101111101011101100010001111111010110101101101...
output:
-173127556 606403598 -50280311 573618753 935287376 495121298 3979773 421325048 633542983 462004056 -532505426 -153180361 -224783626 471060724 741085921 247299595 391757082 -469486168 184945922 1774938 235428115 -175587377 171553338 298994289 962986283 151043620 579879345 659219652 828114595 11565166...
result:
wrong answer wrong answer on query #1: read -173127556 but expected 310305144