Submission #106534

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
using i32=int;using i64=long long;using ll =i64;
#define BR "\n"

#define ALL(c) c.begin(),c.end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

//x,y,z
template <typename T> using X = vector<T>;template <typename T> using Y = vector<T>;template <typename T> using Z = vector<T>;
template <typename T> using YX = Y<X<T>>;//H*W M*N
template <typename T> using ZYX = Z<YX<T>>;

#define H(Map) Map.size()
#define W(Map) Map[0].size()

//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef MODE_DEBUG
#define  DUMP(x)  cerr << #x << " = " << (x) <<endl
#define DEBUG(x) DUMP(x) << " (L" << __LINE__ << ")" << " " << __FILE__<<endl
#define CHECK(exp,act)  if(exp!=act){DUMP(exp);DEBUG(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#else
#define DUMP(x)
#define DEBUG(x)
#define CHECK(exp,act)
#define STOP(e)
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T>>& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)res << p.first<<":" << p.second<<" ";
	ss>>res;return res;
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}


namespace Recursion{
	

	using V=ll;

	//O(m^2*log(n))
	// a[0]=ss[0],...,a[m-1]=ss[m-1]
	//a[n+m]=ms[0]*a[n]+...+ms[m-1]*a[n+m-1]+C
	const ll MOD=1000000007;
	// getnth(n,初項,係数, 定数係数)
	V getnth(ll n,const vector<V> ss, const vector<V> ms,V C=0){
		const int K = ms.size(),M = K * 2 - 1;
		
		vector<bool> binary;
		for(int m=n;m!=0;m/=2)binary.push_back(m % 2==1);
		reverse(binary.begin(), binary.end());

		vector<V> as(M, 0),next(M, 0);
		as[0] = 1;V Cs = 0;
		for(int i=0;i<(int)binary.size();i++){
			fill(ALL(next),0);
			{
				// *2
				// A_2n=ΣΣf_a*f_b*A_(a+b)=Σnext(a+b)*A_(a+b)
				// 係数
				V sum = 1,add = 0;
				for(int a=0;a<K;a++){
					for(int b=0;b<K;b++){
						next[a+b] = mod(next[a+b] + as[a] * as[b],MOD);
					}
					sum =mod(sum + as[a],MOD);
				}
				REP(i,M)as[i] = next[i];

				// M-1 ... K 
				for(int j=M-1;j>=K;j--){
					for(int k=1;k<=K;k++)as[j-k] = mod(as[j-k] + ms[K-k] * as[j] ,MOD) ;
					add = mod(add + as[j],MOD);
					as[j] = 0;
				}
				Cs = mod(Cs * sum+add, MOD);
			}
			if(binary[i]){
				// A_(n+1)=Σf_a*A_(a+1)
				// +1
				vector<V> next(M, 0);
				for(int i=0;i<K;i++)next[i+1] = as[i];
				REP(i,M)as[i] = next[i];
				
				// K
				for(int k=1;k<=K;k++)as[K-k] = mod(as[K-k] + ms[K-k] * as[K],MOD);
				Cs = mod(Cs + as[K],MOD);
				as[K] = 0;
			}
		}
		V res = 0;
		for(int i=0;i<K;i++)res =mod(res + as[i] * ss[i],MOD);
		res = mod(res + Cs * C ,MOD);
		return res;
	}
}


using namespace Recursion;
int main(){
	ll K,N;cin >>K >> N;
	vector<V> ss(K),ms(K);
	fill(ALL(ss),1);fill(ALL(ms),1);

	cout<< getnth(N-1,ss,ms)<<endl;
}

Submission Info

Judge Result