Submission #45429

#TimeUsernameProblemLanguageResultExecution timeMemory
45429choikiwonWindow Xor (KRIII5_WX)C++17
0 / 7
1088 ms15756 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double lf; typedef complex<lf> base; const lf PI = 3.14159265358979; void fft(vector<base> &a, bool inv) { int n = a.size(); for(int i = 1, j = 0; i < n; i++) { int bit = n>>1; for(; j >= bit; bit>>=1) j -= bit; j += bit; if(i < j) swap(a[i], a[j]); } for(int len = 2; len <= n; len <<= 1) { lf ang = 2 * PI / len * (inv? -1 : 1); base wlen(cos(ang), sin(ang)); for(int i = 0; i < n; i += len) { base w(1); for(int j = 0; j < len / 2; j++) { base u = a[i + j], v = a[i + j + len / 2] * w; a[i + j] = u + v; a[i + j + len / 2] = u - v; w *= wlen; } } } if(inv) for(int i = 0; i < n; i++) a[i] /= n; } void multiply(vector<int> &a, vector<int> &b, vector<int> &res) { vector<base> fa(a.begin(), a.end()), fb(b.begin(), b.end()); int n = 1; while(n < max(a.size(), b.size())) n <<= 1; n <<= 1; fa.resize(n); fft(fa, false); fb.resize(n); fft(fb, false); for(int i = 0; i < n; i++) fa[i] *= fb[i]; fft(fa, true); res.resize(n); for(int i = 0; i < n; i++) res[i] = (int)(fa[i].real() + (fa[i].real() > 0? 0.5 : -0.5) ); } int N, K; ll T; vector<int> X, B, C, A, tmp, res; void solve(ll t) { if(t == 1) { B = vector<int>(N, 0); for(int i = 0; i < K; i++) { B[i] = 1; } C = B; return; } solve(t / 2); multiply(B, B, B); for(int i = N; i < 2 * N; i++) { B[i - N] += B[i]; } for(int i = 0; i < N; i++) B[i] %= 2; B.resize(N); if(t % 2) { multiply(B, C, B); for(int i = N; i < 2 * N; i++) { B[i - N] += B[i]; } for(int i = 0; i < N; i++) B[i] %= 2; B.resize(N); } } int main() { scanf("%d %d %lld", &N, &K, &T); X.resize(N); for(int i = 0; i < N; i++) { scanf("%d", &X[i]); } solve(T); reverse(B.begin(), B.end()); res = vector<int>(N, 0); for(int i = 0; i <= 30; i++) { A.resize(N); for(int j = 0; j < N; j++) { A[j] = (X[j] & (1 <<i))? 1 : 0; } multiply(A, B, tmp); for(int j = N; j < 2 * N; j++) tmp[j - N] += tmp[j]; for(int j = 0; j < N; j++) if(tmp[j] % 2) res[ (j + 1) % N ] += (1 << i); } for(int i = 0; i < N; i++) { printf("%d ", res[i]); } }

Compilation message (stderr)

WX.cpp: In function 'void multiply(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
WX.cpp:36:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(n < max(a.size(), b.size())) n <<= 1;
           ~~^~~~~~~~~~~~~~~~~~~~~~~~~
WX.cpp: In function 'int main()':
WX.cpp:80:10: 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:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &X[i]);
         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...