本文最后更新于:2020年4月11日 下午

看见楼下的公式推导,本$czs$顿时非常佩服,但是想让洛谷广大$xxs$看得懂,我就来了。

题目描述

问题就相当于获得以下序列$a$的第$n$项:

A [i] = 1(i <k)

A [i] = A [i-1] + A [i-2] +…+ A [ik](i> = k)

题目分析

  1. 如果使用矩阵求幂,时间复杂度为$O(K^{3N})$,容易超时。
  2. 时间复杂度为$O(K ^ 2 \operatorname{log}N)$查找线性$K$项递归公式的第$n$个项,称为$\operatorname{Kitamasa}$方法。

函数f(m)是返回序列x的函数。序列x 满足A [m] = x [0] A [0] + x [1] A [1] + ... + X [ k-1 ] A [ k-1 ]

如果可以确定f(n),那么也可以确定A [n]

如果可以从f(m)高速获得f(m +1)f(2m),则通过以倍增/迭代平方法的方式进行计算,可以在$O(\operatorname{log}n)$的时间内获得f(n)

从f(m)到f(m +1)通过$O(k)$以下列方式获得。

A[m] = x [0] A [0] + x [1] A [1] + ... + x [ k-1 ] A [ k-1 ]

A [m +1] = x [0] A [ 1] + x [1] A [2] + ... + x [ k-1 ] A [k]= x [0] A [1] + x [1] A [2] + ... + x [ k-1 ] *(A [0] + A [1] + ... + A [ k-1 ])
= x
[ k-1 ] A [0] +(x [0] + x [ k-1 ])A [1 ] +…+(X [k-2] + x [ k-1 ])A [ k-1 ]

如上所述,由于可以从f(m)计算f(m +1)f(2m),因此可以使用$O(k ^ 2logn)$获得第$n$个项。

$Code$

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

vector<ll> dfs(vector<ll> a, vector<ll> d, ll n) {
  ll k = d.size();
  if(n == k) return d;
  vector<ll> ret(k);
  if(n&1 || n<k*2) {
    auto v = dfs(a, d, n-1);
    ret[0] = v[k-1] * a[0] % MOD;
    FOR(i, 1, k) ret[i] = (v[i-1] + v[k-1] * a[i] % MOD) % MOD;
  } else {
    auto v = dfs(a, d, n/2);
    vector<vector<ll>> f(k, vector<ll>(k));
    f[0] = v;
    FOR(i, 1, k) {
      f[i][0] = f[i-1][k-1] * a[0] % MOD;
      FOR(j, 1, k) f[i][j] = (f[i-1][j-1] + f[i-1][k-1] * a[j] % MOD) % MOD;
    }
    REP(i, k) REP(j, k) (ret[i] += v[j] * f[j][i] % MOD) %= MOD;
  }
  return ret;
}
ll kitamasa(vector<ll> a, vector<ll> d, ll n) {
  auto ret = dfs(a, d, n);
  ll ans = 0;
  REP(i, d.size()) (ans += d[i] * ret[i]) %= MOD;
  return ans;
}

signed main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, k;
  cin >> k >> n;
  n--;

  if(n < k) {
    cout << 1 << endl;
    return 0;
  }

  vector<ll> d(k, 1);
  cout << kitamasa(d, d, n) << endl;

  return 0;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT944 【注文の多い高橋商店】 上一篇
题解 AT767 【きんいろクッキー】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。