Submission #103873

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstring>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define PB(e) push_back(e)
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef complex<double> P;
typedef long long ll;

const ll     mod = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

vector<ll> poly_mul(const vector<ll> &x,
                    const vector<ll> &y,
                    const vector<ll> &coef, ll mod)
{
  assert(x.size() == y.size());
  
  int n = x.size() - 1;
  vector<ll> ret(n + 1, 0);
  vector<ll> q  (2 * n, 0);
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      (q[i+j] += x[i] * y[j]) %= mod;
    }
  }
  
  for(int i = 2 * n - 1; i >= n; i--){
    for(int j = 0; j < n; j++){
      (q[i-n+j] += q[i] * coef[j]) %= mod;
    }
  }

  ret[n] = x[n];
  
  for(int i = 0; i < n; i++){
    ret[i] = q[i];
    (ret[n] += y[n] * x[i]) %= mod;
  }
  
  return ret;
}

vector<ll> poly_pow(const vector<ll> &coef, ll N, ll mod){
  vector<ll> p(coef.size(), 0); 
  vector<ll> c(coef.size(), 0);

  c[0] = 1;
  p[1] = 1;
  
  while(N){
    if(N & 1) c = poly_mul(c, p, coef, mod);
    p = poly_mul(p, p, coef, mod);
    N >>= 1;
  }
  return c;
}

int main(){
  int K, N;
  cin >> K >> N;
  
  vector<ll> coef(K + 1, 1); coef[K] = 0;
  coef = poly_pow(coef, N - 1, mod);

  cout << accumulate(ALL(coef), 0LL) % mod<< endl;
  
  return 0;
}

Submission Info

Judge Result