Submission #2207507

---

Source Code Expand

#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
//#define __int64 long long
const ll INF=((ll)1<<40)-1;

struct Mat{
	public:
	vector<vector<ll> >t;
	int g;//行
	int r;//列
	Mat(int a,int b){
		t.resize(a);
		for(int i=0;i<a;i++)t[i].resize(b);
		g=a;
		r=b;
	}



};


	Mat kakeru(Mat a,Mat b){
		if(a.r!=b.g)return Mat(0,0);//異常終了
		
		Mat ret(a.g,b.r);


		for(int i=0;i<a.g;i++){
			for(int j=0;j<b.r;j++){
				ll tmp=0;
				for(int k=0;k<a.r;k++){
					if(k==0)tmp=a.t[i][k]&b.t[k][j];
					else tmp=tmp^(a.t[i][k]&b.t[k][j]);
				}
				ret.t[i][j]=tmp;
			}
		}


		return ret;
	}

ll k,m;
ll a[111111];
ll b[111111];


Mat pow2(Mat mat,ll x){
	
	Mat tmp(mat.g,mat.r);
	rep(i,mat.g){
		rep(j,mat.r)tmp.t[i][j]=mat.t[i][j];
	}

	x--;
	while(x){
		if(1&x){
			tmp=kakeru(tmp,mat);
		}
		mat=kakeru(mat,mat);
		x/=2;
	}
	return tmp;
}
int main(){
	//int x=(6&30)^(2&20)^(5&10);
	//cout<<x;
	cin>>k>>m;
	rep(i,k)cin>>a[i];
	rep(i,k)cin>>b[i];
	
	if(m<=k){
		cout<<a[m-1]<<endl;
		return 0;
	}

	Mat kei(k,k);
	rep(i,k){
		rep(j,k){
			if(i==0)kei.t[i][j]=b[j];
			else if(i==j+1)kei.t[i][j]=INF;
		}
	}

	Mat d(k,1);
	rep(i,k)d.t[i][0]=a[k-1-i];


	kei=pow2(kei,m-k);

	Mat z=kakeru(kei,d);


	/*
	rep(i,k){
		rep(j,k)cout<<kei.t[i][j]<<" ";
		cout<<endl;
	}

	rep(i,z.g){
		rep(j,z.r)cout<<z.t[i][j]<<" ";
		cout<<endl;
	}
	*/

	cout<<z.t[0][0]<<endl;

	return 0;
}

Submission Info

Compile Error

./Main.cpp:17:12: error: ‘__int64’ does not name a type
 #define ll __int64
            ^
./Main.cpp:19:7: note: in expansion of macro ‘ll’
 const ll INF=((ll)1<<40)-1;
       ^
./Main.cpp:17:12: error: ‘__int64’ was not declared in this scope
 #define ll __int64
            ^
./Main.cpp:23:16: note: in expansion of macro ‘ll’
  vector<vector<ll> >t;
                ^
./Main.cpp:23:18: error: template argument 1 is invalid
  vector<vector<ll> >t;
                  ^
./Main.cpp:23:18: error: template argument 2 is invalid
./Main.cpp:23:20: error: template argument 1 is invalid
  vector<vector<ll> >t;
                    ^
./Main.cpp:23:20: error: template argument 2 is invalid
./Main.cpp: In constructor ‘Mat::Mat(int, int)’:
./Main.cpp:27:5: error: request for member ‘resize’ in ‘((Mat*)this)->Mat::t’, which is of non-class type ‘int’
   t.resize(a);
     ^
./Main.cpp:28:26: error: invalid types ‘int[int]’ for array subscript
   for(int i=0;i<a;i++)t[i].resize(b);
                          ^
./Main.cpp...