提出 #66942948

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define bi __int128_t
#define lb(x) ((x)&(-(x)))
#define gp(i,j) (((i)>>(j-1))&1)
#define ppc __builtin_popcount
using namespace std;
const int N=25,MS=1.2e6,mod=998244353;
const ll inf=1e18+10;
void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;}
void Sub(int &a,int b){a-=b;if(a<0) a+=mod;}
void Mul(int &a,int b){a=1ll*a*b%mod;}
int qp(int a,int b){
    int x=1;
    while(b){
        if(b&1) Mul(x,a);
        Mul(a,a);b>>=1;
    }return x;
}
int e[N][N];
int f[N][MS];
int n,m;
void slv(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u][v]++;e[v][u]++;
    }
    for(int i=1;i<=n;i++) f[i][1<<(i-1)]=1;
    int U=(1<<n)-1;int ans=0;
    for(int i=1;i<=U;i++){
        for(int j=1;j<=n;j++){
            if(!f[j][i]) continue;
            for(int k=1;k<=n;k++){
                if((1<<(k-1))==lb(i)){
                    Add(ans,1ll*f[j][i]*e[j][__builtin_ctz(i)+1]%mod);
                    //cout<<i<<' '<<j<<' '<<k<<' '<<f[j][i]<<endl;
                }
                if((i>>(k-1))&1) continue;
                if((1<<(k-1))<lb(i)) continue;
                //cout<<(i|(1<<(k-1)))<<' '<<f[j][i]<<endl;
                Add(f[k][i|(1<<(k-1))],1ll*f[j][i]*e[j][k]%mod);
            }
        }
    }
    //cout<<ans<<endl;
    Sub(ans,m);Mul(ans,(mod+1)/2);
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;//cin>>t;
    while(t--) slv();
    cout.flush();
    return 0;
}

提出情報

ジャッジ結果