Submission #99363

---

Source Code Expand

#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <cstring>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007ll;

ll nth(const vector<ll> init, const vector<ll> coef, ll constant, ll n){
	const int K = coef.size();
	const int M = K * 2 - 1;
	
	vector<int> binary;
	for(int m=n;m;m/=2)binary.push_back(m % 2);
	reverse(binary.begin(), binary.end());

	vector<ll> cs(M, 0);
	cs[0] = 1;
	ll ks = 0;

	for(int i=0;i<binary.size();i++){
		{
			// *2
			vector<ll> next(M, 0);
			ll sum = 1;
			ll add = 0;

			for(int a=0;a<K;a++){
				for(int b=0;b<K;b++){
					next[a+b] = (next[a+b] + cs[a] * cs[b] % MOD) % MOD;
				}
				sum = (sum + cs[a]) % MOD;
			}

			cs = next;
			for(int j=M-1;j>=K;j--){
				for(int k=1;k<=K;k++)cs[j-k] = (cs[j-k] + coef[K-k] * cs[j] % MOD) % MOD;
				add = (add + cs[j]) % MOD;
				cs[j] = 0;
			}

			ks = (ks * sum) % MOD;
			ks = (ks + add) % MOD;
		}

		if(binary[i]){
			// +1
			vector<ll> next(M, 0);
			for(int i=0;i<K;i++)next[i+1] = cs[i];

			cs = next;
			for(int k=1;k<=K;k++)cs[K-k] = (cs[K-k] + coef[K-k] * cs[K] % MOD) % MOD;

			ks = (ks + cs[K]) % MOD;
			cs[K] = 0;
		}
	}

	ll ret = 0;
	for(int i=0;i<K;i++)ret = (ret + cs[i] * init[i] % MOD) % MOD;
	ret = (ret + ks * constant % MOD) % MOD;

	return ret;
}

ll solve(int K, int N){
	const vector<ll> init(K, 1); // 初項
	const vector<ll> coef(K, 1); // 係数
	const ll constant = 0;       // 定数係数

	ll ret = nth(init, coef, constant, N);
	return ret;
}

int main(){
	int K, N;

	cin >> K >> N;
	N--;

	cout << solve(K, N) << endl;
	return 0;
}

Submission Info

Judge Result