Submission #19573281

---

Source Code Expand

#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

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