結果

問題 No.2711 Connecting Lights
コンテスト
ユーザー graythunder1
提出日時 2024-08-25 04:19:24
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,420 bytes
コンパイル時間 1,545 ms
コンパイル使用メモリ 160,640 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-25 04:19:27
合計ジャッジ時間 2,838 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;

#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define rrep(i,a) for(ll i=a-1;i>=0;i--)
#define MOD 998244353

//debug
#define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl;

int main(){
  ll N, M, K;
  cin >> N >> M >> K;

  ll cnt_mat[N+1][N+1];
  rep(i, N+1) rep(j, N+1) cnt_mat[i][j] = 0;
  ll b_tmp;

  rep(b, 1 << N) {
    ll cnt_all = 0, cnt_tmp = 0;
    b_tmp = b;
    rep(i, N) {
      if(b_tmp % 2 == 1) cnt_all++;
      b_tmp /= 2;
    }
    b_tmp = b;
    rep(i, N) {
      if(b_tmp % 2 == 1) cnt_tmp++;
      if(cnt_tmp >= K) cnt_mat[i+1][cnt_all]++;
      b_tmp /= 2;
    }
  }

  ll result[N+1];
  rep(i, N+1) result[i] = 0;
  rep(b, 1 << N) {
    ll cnt = 0;
    ll b_tmp = b;
    rep(i, N) {
      if(b_tmp % 2 == 1) cnt++;
      b_tmp /= 2;
    }
    if(cnt >= K) result[cnt]++;
  }

  repi(i, 1, M) {
    ll result_tmp[N+1];
    rep(j, N+1) result_tmp[j] = 0;
    rep(j, N+1) {
      rep(k, N+1) {
        result_tmp[k] += result[j] * cnt_mat[j][k];
        result_tmp[k] %= MOD;
      }
    }
    copy(result_tmp, result_tmp+N+1, result);
  }

  ll ans = 0;
  rep(i, N+1) {
    ans += result[i];
    ans %= MOD;
  }
  if(M == 1) {
    cout << (1 << N) << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}
0