Submission #342478

---

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)--)
#define MOD 10007
#define M 3

int a[32][2*M-1] = {0,1,0,0,0};

//a(0)からa(2*m-2)の形のa(n)をa(0)からa(m-1)の形に直す
void form(int* n){
	rev(i, M, 2 * M - 1){
		rep(j, 1, M + 1)
			n[i - j] = (n[i - j] + n[i]) % MOD;
		n[i] = 0;
	}
}

void print(int *result){
	rep(j, 0, 3){
		printf("%d ", result[j]);
	}
	cout << endl;
}

void add(int *l, int *r, int *ans){
	//print(l); print(r);
	rep(i, 0, 2 * M - 1){
		ans[i] = 0;
	}
	rep(i,0,M)
		rep(j, 0, M){
			ans[i + j] = (ans[i + j] + (l[i] * r[j]) % MOD) % MOD;
		}
	form(ans);

	//print(ans);
}


//a(2^n)を求める
void init(){
	//初期化
	rep(n, 0, 32){

		//a(2^n)の計算
		add(a[n], a[n], a[n + 1]);
	}
}



int calc(int n){
	int result[5] = { 1 };
	int tmp[5] = { 1 };
	rep(i, 0, 30){
		if (1&(n >> i)){
			add(tmp, a[i], result);
			rep(j, 0, M)tmp[j] = result[j];
		}
	}
	return(result[2]);
}


int main(void){
	int n;
	cin >> n;
	init();		
	cout << calc(n-1) << endl;
}

Submission Info

Judge Result