Submission #342774

---

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 1000000007ll
#define LL long long
LL M;

LL a[33][2 * 1000 - 1];
LL a0[1000];

//a(0)からa(2*m-2)の形のa(n)をa(0)からa(m-1)の形に直す
void form(LL* 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(LL *result){
	rep(j, 0, 3){
		printf("%d ", result[j]);
	}
	cout << endl;
}

void add(LL *l, LL *r, LL *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(i, 0, M){
		a0[i] = 1;
	}
	a[0][1] = 1;
}
LL calc(int n){
	LL result[2000] = { 1 };
	LL tmp[2000] = { 1 };
	int bin = 0;
	while(n){
		if (1 & n){
			add(tmp, a[bin], result);
			rep(j, 0, M)tmp[j] = result[j];
		}
		n >>= 1;
		add(a[bin], a[bin], a[bin + 1]);
		bin++;
	}
	LL ans = 0;
	rep(i, 0, M)
		ans =(ans+ (result[i]*a0[i])%MOD)%MOD;
	return(ans);
}


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

Submission Info

Judge Result