Submission #340433

---

Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
/*
int dp[3] = {1,0,0};
int N;
int main(void){
	cin >> N;
	N++;
	rep(i, 4, N){
		dp[i % 3] += dp[(i + 1) % 3] + dp[(i + 2) % 3];
		if (dp[i % 3] >= 10007)dp[i % 3] %= 10007;
	}
	cout << dp[(--N) % 3] << endl;
}

*/
int bit[20][3][3] = { { { 1, 1, 1 }, { 1, 0, 0 }, { 0, 1, 0 } } };
int tmp[21][3][3] = { { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } } };
int e[3][3] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
int N;
void calc(int a[3][3], int b[3][3], int c[3][3]){
	rep(i, 0, 3)rep(j, 0, 3){
		c[i][j] = 0;
		rep(k, 0, 3)c[i][j] += a[i][k] * b[k][j];
		c[i][j] %= 10007;
	}
}

void init(){

	rep(i, 1, 20){
		calc(bit[i - 1], bit[i - 1], bit[i]);
	}
}

int main(void){
	init();
	cin >> N;
	switch (N){
	case 1:
	case 2:
	case 3:cout << tmp[0][0][3 - N] << endl; break;
	default:N -= 3;
		rep(i, 0, 20){
			if ((N >> i) & 1)
				calc(tmp[i], bit[i], tmp[i + 1]);
			else
				calc(tmp[i], e, tmp[i + 1]);
		}
		/*
		rep(i, 0, 3){
			rep(j, 0, 3){
				printf("%d ", tmp[10][i][j]);
			}
			cout << endl;
		}
		*/
		cout << tmp[20][0][0] << endl;
		break;
	}
}

Submission Info

Judge Result