Submission #1779302
Source Code Expand
#include<bits/stdc++.h> using namespace std; using ll = int64_t; using matrix = vector<vector<ll> >; matrix E; matrix po(matrix &a, matrix &b){ matrix ret; for(ll i = 0; i < a.size(); ++i){ vector<ll> yo; for(ll j = 0; j < b[0].size(); ++j){ ll c = 0; for(ll k = 0; k < b.size(); ++k)c ^= (a[i][k] & b[k][j]); yo.push_back(c); } ret.push_back(yo); } return ret; } matrix pow(matrix &a, ll b){ matrix yo[30] = {a}; for(ll i = 1; i < 30; ++i) yo[i] = po(yo[i - 1], yo[i - 1]); matrix ret = E; for(ll i = 0; b; ++i){ if(b & 1) ret = po(yo[i], ret); b /= 2; } return ret; } int main(){ ll k, m; cin >> k >> m; ll a[k], c[k]; ll anabi = (ll)pow(2, 32) - 1; for(ll i = 0; i < 2 * k; ++i) cin >> (i / k ? c : a)[i % k]; for(ll i = 0; i < k; ++i){ vector<ll> yo; for(ll j = 0; j < k; ++j) yo.push_back((i == j ? anabi : 0)); E.push_back(yo); } matrix sina, pomu; vector<ll> mon; for(ll i = 0; i < k; ++i){ mon.push_back(c[i]); vector<ll> purin; purin.push_back(a[k - 1 - i]); pomu.push_back(purin); } sina.push_back(mon); for(ll i = 1; i < k; ++i){ vector<ll> pinya; for(ll j = 0; j < k; ++j)pinya.push_back((i - 1 == j ? anabi : 0)); sina.push_back(pinya); } matrix temp = pow(sina, m - k); matrix ans = po(temp, pomu); for(int i = 0; i < ans.size(); ++i) cout << ans[0][i] << ", "; cout << endl; cout << ans[0][0] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 漸化式 |
User | kcvlex |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1456 Byte |
Status | WA |
Exec Time | 57 ms |
Memory | 3072 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 0 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, sample_1.txt, sample_2.txt, sample_3.txt, small_1.txt, small_2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
random_01.txt | WA | 1 ms | 256 KB |
random_02.txt | WA | 1 ms | 256 KB |
random_03.txt | WA | 1 ms | 256 KB |
random_04.txt | WA | 1 ms | 256 KB |
random_05.txt | WA | 2 ms | 256 KB |
random_06.txt | WA | 2 ms | 384 KB |
random_07.txt | WA | 4 ms | 640 KB |
random_08.txt | WA | 10 ms | 1024 KB |
random_09.txt | WA | 55 ms | 3072 KB |
random_10.txt | WA | 57 ms | 3072 KB |
random_11.txt | WA | 57 ms | 3072 KB |
random_12.txt | WA | 57 ms | 3072 KB |
random_13.txt | WA | 57 ms | 3072 KB |
random_14.txt | WA | 56 ms | 3072 KB |
random_15.txt | WA | 54 ms | 3072 KB |
sample_1.txt | WA | 1 ms | 256 KB |
sample_2.txt | WA | 1 ms | 256 KB |
sample_3.txt | WA | 3 ms | 512 KB |
small_1.txt | WA | 1 ms | 256 KB |
small_2.txt | WA | 1 ms | 256 KB |