#include<cstdio>
#include<vector>
#include<complex>
#include<algorithm>
using namespace std;
const int NMAX = 100001;
const double PI = atan2(1, 0) * 2;
typedef complex<double> idouble;
typedef vector<idouble> poly;
typedef vector<int> vi;
int rev(int x, int sz) {
int i, r = 0;
for (i = 0; i < sz; i++) {
r = r << 1 | x & 1;
x >>= 1;
}
return r;
}
void fft(poly& a, bool f = false) {
const int N = a.size();
int sz = 0, t = 1;
while (t < N) sz++, t <<= 1;
idouble x, y, z;
double w;
int i, j, k;
for (i = 0; i < N; i++) {
j = rev(i, sz);
if (i < j) {
z = a[i];
a[i] = a[j];
a[j] = z;
}
}
for (i = 1; i < N; i <<= 1) {
w = PI / i;
if (f) w = -w;
x = idouble(cos(w), sin(w));
for (j = 0; j < N; j += i << 1) {
y = idouble(1);
for (k = 0; k < i; k++) {
z = a[i + j + k] * y;
a[i + j + k] = a[j + k] - z;
a[j + k] += z;
y *= x;
}
}
}
if (f) for (i = 0; i < N; i++) a[i] /= N;
}
vi mult(const vi& A, const vi& B) {
int t = max(A.size(), B.size());
int N = 1; for (; N<t; N <<= 1); N <<= 1;
poly a(N), b(N);
for (int i = 0; i<A.size(); i++) a[i] = A[i];
for (int i = 0; i<B.size(); i++) b[i] = B[i];
fft(a); fft(b);
poly ab(N);
for (int i = 0; i<N; i++) ab[i] = a[i] * b[i];
fft(ab, true);
vi tmp(N);
for (int i = 0; i < N; i++)
tmp[i] = ((int)(ab[i].real() + 0.5)) & 1;
vi ret(t);
for (int i = 0; i < N; i++) {
int j = i; while (j >= t) j -= t;
ret[j] ^= tmp[i];
}
return ret;
}
typedef long long ll;
int A[NMAX];
vi polypow(const vi& V, ll y) {
if (y == 1) return V;
if (y % 2) return mult(polypow(V, y - 1), V);
vi VV = polypow(V, y >> 1);
return mult(VV, VV);
}
int ans[NMAX];
int main() {
int N, K; ll T;
scanf("%d%d%lld", &N, &K, &T);
for (int i = 0; i < N; i++) scanf("%d", A + i);
vi base(N);
for (int i = 0; i < K; i++) base[i] = 1;
vi trans = polypow(base, T);
for (int bit = 0; bit < 31; bit++) {
vi cur(N);
for (int i = 0; i < N; i++) cur[i] = (A[i] & (1 << bit)) ? 1 : 0;
auto res = mult(cur, trans);
for (int i = 0; i < N; i++) if (res[i]) ans[i] ^= (1 << bit);
}
for (int i = 0; i < N; i++) printf("%d ", ans[i]);
}
Compilation message
WX.cpp: In function 'int rev(int, int)':
WX.cpp:17:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
r = r << 1 | x & 1;
^
WX.cpp: In function 'vi mult(const vi&, const vi&)':
WX.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i<A.size(); i++) a[i] = A[i];
^
WX.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i<B.size(); i++) b[i] = B[i];
^
WX.cpp: In function 'int main()':
WX.cpp:94:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &N, &K, &T);
^
WX.cpp:95:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; i++) scanf("%d", A + i);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2760 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2760 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2760 KB |
Output is correct |
| 4 |
Execution timed out |
1000 ms |
17324 KB |
Execution timed out |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17324 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
