Submission #19573281


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){
        if(n < k) return a[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);
    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 3336 Byte
Status AC
Exec Time 132 ms
Memory 82136 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 132 ms 82136 KB
01 AC 78 ms 45712 KB
02 AC 127 ms 81948 KB
03 AC 32 ms 16584 KB
04 AC 5 ms 3468 KB
90 AC 2 ms 3508 KB
91 AC 2 ms 3520 KB