#1178835 (C++23(gcc16)) No.2711 Connecting Lights

• 問題: No.2711 Connecting Lights
• ユーザー: Rumain831
• 提出日時: 2026-08-25 04:46:08
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 5 ms / 5,000 ms
• コード長: 2,617 bytes
• コンパイル時間: 1,903 ms
• コンパイル使用メモリ: 183,528 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-25 04:46:23
• 合計ジャッジ時間: 4,071 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
ll mod = 998244353;

struct Matrix{
  int r, c;
  vector<vector<ll>> a;
  Matrix(int r, int c) :r(r), c(c), a(r, vector<ll>(c, 0)){}
  
  static Matrix iden(int n){ //正方行列限定
    Matrix I(n, n);
    for(int i=0; i<n; i++) I.a[i][i]=1;
    return I;
  }

  // --- 加算・減算 ---
  Matrix& operator+=(const Matrix& rhs) {
    //assert(r==rhs.r&&c==rhs.c);
    for(int i=0; i<r; i++)for(int j=0; j<c; j++){
      a[i][j]+=rhs.a[i][j];
      if(a[i][j]>=mod) a[i][j]-=mod;
    }
    return *this;
  }
  Matrix& operator-=(const Matrix& rhs) {
    //assert(r==rhs.r&&c==rhs.c);
    for(int i=0; i<r; i++)for(int j=0; j<c; j++){
      a[i][j]-=rhs.a[i][j];
      if(a[i][j]<0) a[i][j]+=mod;
    }
    return *this;
  }
  friend Matrix operator+(Matrix lhs, const Matrix& rhs){return lhs+=rhs;}
  friend Matrix operator-(Matrix lhs, const Matrix& rhs){return lhs-=rhs;}

  Matrix operator*(const Matrix& rhs) const { //base*rhs
    //assert(c==rhs.r);
    Matrix ans(r, rhs.c);
    for(int i=0; i<r; i++){
      for(int k=0; k<c; k++){
        if(a[i][k]==0) continue;
        for(int j=0; j<rhs.c; j++){
          ans.a[i][j]+=a[i][k]*rhs.a[k][j];
          ans.a[i][j]=(ans.a[i][j]%mod+mod)%mod;
        }
      }
    }
    return ans;
  }

  Matrix& operator*=(const Matrix& rhs){return *this=(*this)*rhs;}

  // --- ベクトルとの積 (列ベクトル) ---
  vector<ll> mul_vec(const vector<ll>& v) const {
    //assert(c == (int)v.size());
    vector<ll> res(r, 0);
    for(int i=0;i<r;i++){
      __int128 acc = 0;
      for(int j=0;j<c;j++){
        acc += (__int128)a[i][j] * v[j];
      }
      res[i] = (ll)(acc % mod);
    }
    return res;
  }

  // --- 転置 ---
  Matrix transpose() const {
    Matrix t(c, r);
    for(int i=0;i<r;i++)for(int j=0;j<c;j++) t.a[j][i] = a[i][j];
    return t;
  }

  friend ostream& operator<<(ostream& os, const Matrix& M){
    for(int i=0;i<M.r;i++){
      for(int j=0;j<M.c;j++){
        os << M.a[i][j] << (j+1==M.c?'\n':' ');
      }
    }
    return os;
  }
};

Matrix pow(Matrix A, ll k){
  Matrix R(A.r, A.r);
  R=R.iden(A.r);
  while(k){
    if(k&1) R=A*R;
    A=A*A;
    k>>=1;
  }
  return R;
}

int main(void){
  int n, m, k; cin >> n >> m >> k;
  int mx=(1<<n);
  Matrix A(mx, mx);
  for(int i=0; i<mx; i++)for(int j=0; j<mx; j++){
    int x=__builtin_popcount(i&j);
    if(x>=k) A.a[i][j]=1;
  }
  auto B=pow(A, m-1);
  vector<ll> p(mx, 1);
  auto v=B.mul_vec(p);
  ll ans=0;
  for(auto p:v) ans+=p, ans%=mod;
  cout << ans << endl;
  return 0;
}