Submission #19569663


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
#define all(s) (s).begin(),(s).end()
#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define se second
//const ll mod = 998244353;
const ll mod = 1000000007;
const ll inf = 2000000000000000000ll;
static const long double pi = 3.141592653589793;
template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;}
template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;}
ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
vector<ll> one(vector<ll> x,vector<ll> d){
  ll k=x.size();
  vector<ll> res(k);
  for(int i=0;i<k;i++){
    if(i==0){
      res[i]=d[i]*x[k-1]%mod;
    }
    else{
      res[i]=(x[i-1]+d[i]*x[k-1])%mod;
    }
  }
  return res;
}
vector<ll> two(vector<ll> x,vector<ll> d){
  ll k=x.size();
  vector<vector<ll>> tmp(k,vector<ll>(k));
  vector<ll> y=x;
  for(int i=0;i<k;i++){
    tmp[i]=y;
    y=one(y,d);
  }
  vector<ll> res(k);
  for(int i=0;i<k;i++){
    ll p=x[i];
    for(int j=0;j<k;j++){
      res[j]+=p*tmp[i][j];
      res[j]%=mod;
    }
  }
  return res;
}
vector<ll> mulpow(vector<ll> d,ll n){
  ll k=d.size();
  vector<ll> res(k);
  vector<ll> t;
  while(n!=k){
    if(n%2==0&&n/2>=k){
      t.push_back(1);
      n/=2;
    }
    else{
      t.push_back(0);
      n--;
    }
  }
  rever(t);
  vector<ll> v=d;
  for(int i=0;i<int(t.size());i++){
    if(t[i]==0){
      v=one(v,d);
    }
    else{
      v=two(v,d);
    }
  }
  return v;
}
int main() {
  /* mod は 1e9+7 */
  ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
  cout<< fixed << setprecision(10);
  ll k,n;
  cin>>k>>n;
  vector<ll> s(k,1);
  if(k>=n){
    cout<<1<<endl;
    return 0;
  }
  s=mulpow(s,n-1);
  ll ans=0;
  for(int i=0;i<k;i++){
    ans+=s[i];
    ans%=mod;
  }
  cout<<ans<<endl;
}

Submission Info

Submission Time
Task T - フィボナッチ
User PCTprobability
Language C++ (GCC 9.2.1)
Score 8
Code Size 2347 Byte
Status AC
Exec Time 164 ms
Memory 11296 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 155 ms 11124 KB
01 AC 95 ms 8196 KB
02 AC 164 ms 11296 KB
03 AC 36 ms 4396 KB
04 AC 3 ms 3528 KB
90 AC 2 ms 3596 KB
91 AC 2 ms 3580 KB