#1179241 (C++23) No.2711 Connecting Lights

• 問題: No.2711 Connecting Lights
• ユーザー: vjudge1
• 提出日時: 2026-08-25 23:34:09
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 74 ms / 5,000 ms
• コード長: 3,445 bytes
• コンパイル時間: 2,941 ms
• コンパイル使用メモリ: 373,008 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-25 23:34:16
• 合計ジャッジ時間: 5,002 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#pragma optimize("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define ll int
#define int long long 
#define pb push_back
#define F first
#define S second
#define ld long double
#define all(v) v.begin(),v.end()    
#define rall(v) v.rbegin(),v.rend()
#define maxel(v) *max_element(all(v))
#define minel(v) *min_element(all(v))
#define endl '\n'

const int N=1e6+67,mod=1e9+7,INF=1e18+1488;

vector<int> prefix_func(string s){
    int n=s.size();
    vector<int> pi(n);
    pi[0]=0;
    for(int i=1;i<n;i++){
        int j=pi[i-1];
        while(j>0 && s[i]!=s[j]){
            j=pi[j-1];
        }
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
    return pi;
}

int binpow(int a,int b,int MOD){
    a%=MOD;
    int res=1;
    while(b>0){
        if(b&1)res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}

int inv(int a,int MOD){
    return binpow(a,MOD-2,MOD);
}

vector<int> fact,invfact;
void precompute(int MOD){
    fact.assign(N,1);
    invfact.assign(N,1);
    for(int i=1;i<N;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    invfact[N-1]=inv(fact[N-1],MOD);
    for(int i=N-2;i>=0;i--){
        invfact[i]=invfact[i+1]*(i+1)%MOD;
    }
}

int nCr(int n,int k,int MOD){
    if(k<0||k>n)return 0;
    return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;
}

int nPr(int n,int k,int MOD){
    if(k<0||k>n)return 0;
    return fact[n]*invfact[n-k]%MOD;
}

int gcd(int a,int b){
    while(b){
        a%=b;
        swap(a,b);
    }
    return a;
}

int lcm(int a,int b){
    if(a==0||b==0)return 0;
    return a/gcd(a,b)*b;
}
struct DSU{
    vector<int> p,sz;
    int comp;
    DSU(int n){
        p.resize(n+1);
        sz.assign(n+1,1);
        for(int i=1;i<=n;i++)p[i]=i;
        comp=n;
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
    void unite(int a,int b){
        a=get(a);
        b=get(b);
        if(a!=b){
            if(sz[b]>sz[a])swap(a,b);
            p[b]=a;
            sz[a]+=sz[b];
            comp--;
        }
    }
};

vector<int> primes;
vector<bool> is_comp;
void sieve(int n){
    is_comp.assign(n+1,false);
    if(n>=2)primes.pb(2);
    for(int i=3;i<=n;i+=2){
        if(!is_comp[i]){
            primes.pb(i);
            for(int j=i*i;j<=n;j+=2*i){
                is_comp[j]=true;
            }
        }
    }
}

int phi(int a){
    int r=a;
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            while(a%i==0)a/=i;
            r-=r/i;
        }
    }
    if(a>1)r-=r/a;
    return r;
}
int countD(int n) {
    int cnt=0;
    for(int i=1;i*i<=n;++i){
        if(n%i==0){
            if (i*i==n){
				cnt+=1;
			}
            else{
				cnt += 2;
			}
        }
    }
    return cnt;
}
void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	int md=998244353;
	int s=1<<n;
	vector<int> d(s,1);
	for(int j=1;j<m;j++){
		vector<int> nd(s,0);
		for(int m2=0;m2<s;m2++){
			for(int m1=0;m1<s;m1++){
				if(__builtin_popcount(m1&m2)>=k){
					nd[m2]=(nd[m2]+d[m1])%md;
				}
			}
		}
		d=nd;
	}
	int ans=0;
	for(int i=0;i<s;i++){
		ans=(ans+d[i])%md;
	}
	cout<<ans<<endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.in","r",stdin); freopen("output.out","w",stdout);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}