結果
問題 |
No.2711 Connecting Lights
|
ユーザー |
|
提出日時 | 2024-03-31 14:55:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 5,000 ms |
コード長 | 1,378 bytes |
コンパイル時間 | 2,145 ms |
コンパイル使用メモリ | 199,676 KB |
最終ジャッジ日時 | 2025-02-20 17:31:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; template<class T> using graph=vector<vector<T>>; template<class T> using min_priority_queue=priority_queue<T,vector<T>,greater<T>>; constexpr int INF32=INT_MAX/2; constexpr ll INF64=1LL<<60; constexpr array<int,4> DX4={0,1,0,-1}; constexpr array<int,4> DY4={-1,0,1,0}; constexpr array<int,8> DX8={0,1,1,1,0,-1,-1,-1}; constexpr array<int,8> DY8={-1,-1,0,1,1,1,0,-1}; inline int popcnt(ll n){return __builtin_popcountll(n);} template<class T> inline bool chmax(T& a,const T& b){return a<b?a=b,true:false;} template<class T> inline bool chmin(T& a,const T& b){return b<a?a=b,true:false;} #define rep(i,s,n) for(ll i=(ll)(s);i<(ll)(n);i++) #define rrep(i,s,n) for(ll i=(ll)(s);i>=(ll)(n);i--) void _main(); int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); cout<<fixed<<setprecision(16); _main(); } #include <atcoder/modint> using mint = atcoder::modint998244353; void _main(){ int N, M, K; cin >> N >> M >> K; vector dp(M, vector<mint>(1U<<N)); for(unsigned s=0; s<(1U<<N); s++) dp[0][s] = mint(1); rep(i,1,M){ for(unsigned s=0; s<(1U<<N); s++) if(K<=popcnt(s)){ for(unsigned ns=0; ns<(1U<<N); ns++) if(K<=popcnt(ns&s)){ dp[i][ns] += dp[i-1][s]; } } } mint ans = 0; for(unsigned s=0; s<(1U<<N); s++) ans += dp[M-1][s]; cout << ans.val() << endl; }