Submission #3413677
Source Code Expand
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)
#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;
VV mul(VV &a, VV &b){
VV c(a.size(),V(b[0].size()));
rep(i,a.size()){
rep(k,b.size()){
rep(j,b[0].size()){
c[i][j] = (c[i][j] xor (a[i][k] bitand b[k][j]));
}
}
}
return c;
}
VV power(VV a, int n){
VV b(a.size(), V(a.size(),0));
rep(i,b.size()) b[i][i] = -1;
while(n>0){
if(n&1) b=mul(b,a);
a = mul(a,a);
n>>=1;
}
return b;
}
int solve(int n, VV A, V C){
VV a(A.size(), V(A.size(),0));
rrep(i,C.size()-1){
a[0][i] = C[i];
}
rep(i,C.size()-1){
a[i+1][i] = -1;
}
a = power(a,n);
VV res = mul(a,A);
return res[0][0];
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int K, M;
cin>>K>>M;
VV A(K,V(1));
V C(K);
rep(i,K) cin>>A[K-i-1][0];
rep(i,K) cin>>C[i];
if(M<=K){
cout1(A[K-M][0]);
}else{
cout1(solve(M-K,A,C));
}
}
Submission Info
Submission Time |
|
Task |
D - 漸化式 |
User |
mensan_fukuhara |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2698 Byte |
Status |
WA |
Exec Time |
50 ms |
Memory |
468 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 |
1 ms |
256 KB |
random_06.txt |
WA |
1 ms |
256 KB |
random_07.txt |
WA |
3 ms |
256 KB |
random_08.txt |
WA |
8 ms |
256 KB |
random_09.txt |
WA |
49 ms |
468 KB |
random_10.txt |
WA |
50 ms |
384 KB |
random_11.txt |
WA |
50 ms |
384 KB |
random_12.txt |
WA |
50 ms |
384 KB |
random_13.txt |
WA |
50 ms |
384 KB |
random_14.txt |
WA |
50 ms |
384 KB |
random_15.txt |
WA |
47 ms |
384 KB |
sample_1.txt |
AC |
1 ms |
256 KB |
sample_2.txt |
WA |
1 ms |
256 KB |
sample_3.txt |
AC |
3 ms |
256 KB |
small_1.txt |
AC |
1 ms |
256 KB |
small_2.txt |
AC |
1 ms |
256 KB |