Submission #98365

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;
const ll MOD = 1000000007;

typedef ll val_t;
typedef vector<val_t> poly_t;

#define NOR(x) ((x) % MOD)

poly_t poly_pow(const poly_t &a, ll k) {
  int n = a.size() - 1;
  poly_t p(n + 1), q(n * 2);
  p[0] = 1;
  for (int s = sizeof(ll) * 8 - __builtin_clzll(k) - 1; s >= 0; s--) {
    rep (i, n * 2) q[i] = 0;
    val_t r = p[n];
    int d = (k >> s) & 1;
    rep (i, n) {
      rep (j, n) q[i + j + d] = NOR(q[i + j + d] + p[i] * p[j]);
      r = NOR(r + p[i] * p[n]);
    }
    for (int i = 2 * n - 1; i >= n; i--) {
      rep (j, n) q[i - n + j] = NOR(q[i - n + j] + q[i] * a[j]);
      r = NOR(r + q[i] * a[n]);
    }
    rep (i, n) p[i] = q[i];
    p[n] = r;
  }
  return p;
}

ll solve(int K, int N) {
  if (N <= K) return 1;

  vector<ll> A(K + 1);
  rep (i, K) A[i] = 1;

  A = poly_pow(A, N - 1);
  ll s = 0;
  rep (i, K) (s += A[i]) %= MOD;
  return (s + MOD) % MOD;
}

ll solve_naive(int K, int N) {
  vector<ll> A(N + 10);
  for (int i = 1; i <= K; ++i) A[i] = 1;
  for (int i = K + 1; i <= N; ++i) {
    A[i] = 0;
    for (int j = 1; j <= K; ++j) (A[i] += A[i - j]) %= MOD;
  }
  return A[N];
}

int main() {
  int K, N;
  while (2 == scanf("%d%d", &K, &N)) {
    printf("%lld\n", solve(K, N));
    // assert(solve(K, N) == solve_naive(K, N));
  }

  return 0;
}

Submission Info

Judge Result