Submission #19573263


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#pragma region atcoder
#include <atcoder/modint>
using namespace atcoder;
//using mint = modint998244353;
using mint = modint1000000007;
#pragma endregion
#pragma region debug for var, v, vv
#define debug(var)  do{std::cerr << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cerr << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){cerr << endl;int cnt = 0;for(const auto& v : vv){cerr << cnt << "th : "; view(v); cnt++;} cerr << endl;}
#pragma endregion
using ll = long long;
const ll mod = 1000000007;
const int inf = 1001001001;
const ll INF = 1001001001001001001ll; 
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
template<class T, class K>bool chmax(T &a, const K b) { if (a<b) { a=b; return 1; } return 0; }
template<class T, class K>bool chmin(T &a, const K b) { if (b<a) { a=b; return 1; } return 0; }
ll rudiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } //  20 / 3 == 7
ll rddiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // -20 / 3 == -7
ll power(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a;} a = a * a; p >>= 1;} return ret;}
ll modpow(ll a, ll p, ll m){ll ret = 1; while(p){if(p & 1){ret = ret * a % m;} a = a * a % m; p >>= 1;} return ret;}
/*---------------------------------------------------------------------------------------------------------------------------------*/
template<typename T>
class Kitamasa{
// 0-indexed
// a[i + k] = d[i] * a[i] + ... + d[i + k - 1] * a[i + k - 1]
private:
    vector<T> a;
    vector<T> d;
    int k;
    // return the coefficient vector of a[n - 1]
    vector<T> solve(ll n){
        if(n == k) return d;
        vector<T> res(k);
        if(n & 1 || n < k * 2){
            vector<T> tmp = solve(n - 1);
            for(int i = 0; i < k; i++) res[i] = d[i] * tmp[k - 1];
            for(int i = 0; i + 1 < k; i++) res[i + 1] += tmp[i];
        }
        else{
            vector<vector<T>> tmp(k, vector<T>(k));
            tmp[0] = solve(n >> 1);
            for(int i = 0; i + 1 < k; i++){
                for(int j = 0; j < k; j++) tmp[i + 1][j] = d[j] * tmp[i][k - 1];
                for(int j = 0; j + 1 < k; j++) tmp[i + 1][j + 1] += tmp[i][j];
            }
            for(int i = 0; i < k; i++){
                for(int j = 0; j < k; j++){
                    res[j] += tmp[0][i] * tmp[i][j];
                }
            }
        }
        return res;
    }
public:
    Kitamasa(vector<T> &_a, vector<T> &_d) : a(_a), d(_d), k((int)a.size()){}
    
    // return a[n - 1]
    T calculate(ll n){
        vector<T> x = solve(n);
        T res = 0;
        for(int i = 0; i < k; i++) res += x[i] * a[i];
        return res;
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);
    ll k, n; cin >> k >> n;
    vector<mint> a(k, 1);
    Kitamasa<mint> kitamasa(a, a);
    if(n <= k) cout << 1 << endl;
    else cout << kitamasa.calculate(n - 1).val() << endl;
}       
/*
   * review you code when you get WA (typo? index?)
   * int overflow, array bounds
   * special cases (n=1?)
*/

Submission Info

Submission Time
Task T - フィボナッチ
User Sooh
Language C++ (GCC 9.2.1)
Score 8
Code Size 3344 Byte
Status AC
Exec Time 130 ms
Memory 82140 KB

Compile Error

./Main.cpp:3: warning: ignoring #pragma region atcoder [-Wunknown-pragmas]
    3 | #pragma region atcoder
      | 
./Main.cpp:8: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
    8 | #pragma endregion
      | 
./Main.cpp:9: warning: ignoring #pragma region debug [-Wunknown-pragmas]
    9 | #pragma region debug for var, v, vv
      | 
./Main.cpp:14: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
   14 | #pragma endregion
      | 

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 130 ms 82140 KB
01 AC 77 ms 45668 KB
02 AC 128 ms 81900 KB
03 AC 34 ms 16572 KB
04 AC 9 ms 3604 KB
90 AC 2 ms 3460 KB
91 AC 2 ms 3572 KB