#1198924 (C++17) No.3799 1 + 6 = 7 (Another version)

• 問題: No.3799 1 + 6 = 7 (Another version)
• ユーザー: 👑 Nachia
• 提出日時: 2026-11-13 22:58:30
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 7,255 bytes
• コンパイル時間: 636 ms
• コンパイル使用メモリ: 103,372 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-11-13 22:58:33
• 合計ジャッジ時間: 2,829 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
using Mint = nachia::StaticModint<998244353>;

#include <ostream>

namespace nachia{

template<class Elem>
struct MatrixModulo{
private:
    int h;
    int w;
    std::vector<Elem> elems;
public:
    
    MatrixModulo(int new_h=0, int new_w=0)
        : h(new_h), w(new_w), elems(h*w, Elem(0)){}
    MatrixModulo(const MatrixModulo &) = default;
    int numRow() const { return h; }
    int numColumn() const { return w; }
    int height() const { return numRow(); }
    int width() const { return numColumn(); }
    typename std::vector<Elem>::iterator operator[](int y){ return elems.begin() + (y*w); }
    typename std::vector<Elem>::const_iterator operator[](int y) const { return elems.begin() + (y*w); }
    static MatrixModulo Identity(int n){
        auto res = MatrixModulo(n,n);
        for(int i=0; i<n; i++) res[i][i]=Elem(1);
        return res;
    }
    MatrixModulo transposed() const {
        auto res = MatrixModulo(w,h);
        for(int i=0; i<h; i++) for(int j=0; j<w; j++) res[j][i] = elems[i*w+j];
        return res;
    }
    void swapColumns(int x1, int x2){
        assert(0 <= x1 && x1 < numColumn());
        assert(0 <= x2 && x2 < numColumn());
        for(int y=0; y<numRow(); y++) std::swap((*this)[y][x1], (*this)[y][x2]);
    }
    void swapRows(int y1, int y2){
        assert(0 <= y1 && y1 < numRow());
        assert(0 <= y2 && y2 < numRow());
        for(int x=0; x<numColumn(); x++) std::swap((*this)[y1][x], (*this)[y2][x]);
    }
    MatrixModulo operator*(const MatrixModulo& r) const {
        assert(width() == r.height());
        auto res = MatrixModulo(h, r.w);
        for(int i=0; i<h; i++) for(int j=0; j<w; j++) for(int k=0; k<r.w; k++){
            res[i][k] += (*this)[i][j] * r[j][k];
        }
        return res;
    }
    std::vector<Elem> operator*(const std::vector<Elem>& r) const {
        assert(width() == int(r.size()));
        auto res = std::vector<Elem>(h);
        for(int i=0; i<h; i++) for(int j=0; j<w; j++){
            res[i] += (*this)[i][j] * r[j];
        }
        return res;
    }
    MatrixModulo& operator*=(const Elem& r){
        int z = (int)elems.size();
        for(int i=0; i<z; i++) elems[i] *= r;
        return *this;
    }
    Elem det() const {
        assert(height() == width());
        MatrixModulo g = *this;
        Elem ans = 1;
        for(int i=0; i<h; i++){
            int tg = -1;
            for(int j=i; j<h; j++){ if(g[j][i].val() != 0) tg = j; }
            if(tg == -1) return 0;
            if(tg != i) ans = -ans;
            for(int j=0; j<h; j++) std::swap(g[i][j], g[tg][j]);
            tg = i;
            ans *= g[i][i];
            Elem const_coeff = g[i][i].inv();
            for(int j=0; j<h; j++) g[i][j] *= const_coeff;
            for(int j=i+1; j<h; j++) for(int k=h-1; k>=i; k--) g[j][k] -= g[j][i] * g[i][k];
        }
        return ans;
    }
    int rank() const {
        if(height() == 0 || width() == 0) return 0;
        MatrixModulo g = *this;
        int y = 0;
        for(int d=0; d<w; d++){
            if(y == h) break;
            int tg = -1;
            for(int i=y; i<h; i++){ if(g[i][d].val() != 0){ tg = i; break; } }
            if(tg == -1) continue;
            for(int j=d; j<w; j++) std::swap(g[y][j], g[tg][j]);
            tg = y;
            Elem const_coeff = g[y][d].inv();
            for(int j=d; j<w; j++) g[y][j] *= const_coeff;
            for(int i=y+1; i<h; i++) for(int j=w-1; j>=d; j--) g[i][j] -= g[i][d] * g[y][j];
            y++;
        }
        return y;
    }
    MatrixModulo pow(unsigned long long i){
        auto a = *this;
        auto res = Identity(height());
        while(i){
            if(i%2) res = res * a;
            a = a * a; i /= 2;
        }
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const MatrixModulo& a){
        int n = a.height(), m = a.width();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(j) os << " ";
                os << a[i][j].val();
            } os << "\n";
        }
        return os;
    }
};


} // namespace nachia
using Mat = nachia::MatrixModulo<Mint>;

void testcase(){
  ll N, M; cin >> N >> M;
  Mat A(2,2);
  A[0][1] = M;
  A[1][1] = M-1;
  A[1][0] = 1;
  cout << A.pow(N)[0][0].val() << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}