結果

問題 No.1116 Cycles of Dense Graph
コンテスト
ユーザー Drice
提出日時 2020-07-18 16:10:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 100 ms / 2,000 ms
コード長 3,665 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 36,444 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 16:22:17
合計ジャッジ時間 2,492 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
//can be done by prefix sum
const long long mod = 998244353;
struct Edge{
    int u,v;
};
Edge e[35];
long long f[200005], invf[200005];
//sum[i][j]: i segment & j node used
long long sum[40][40];
Edge edge[35];
int in[100005];
int queue[50];

long long power(long long a,long long b){
    long long res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b /= 2;
    }
    return res;
}

long long inv(long long u){ return power(u,mod-2); }

long long comb(int n,int m){
    if(m>n || m<0) return 0;
    else{
        return f[n]*invf[n-m]%mod*invf[m]%mod;
    }
}

int min(int a,int b){ return a>b?b:a; }

int max(int a,int b){ return a>b?a:b; }

void preWork(int n,int m){
    f[0] = invf[0] = 1;
    for(long long i = 1; i <= 2*n; i++){ 
        f[i] = f[i-1]*i%mod;
        invf[i] = inv(f[i]);
    }
    for(int i = 1; i <= m; i++){
        for(int j = 2; j <= 2*m; j++){
            sum[i][j] = 0;
            int start = -1;
            if(j==2) start = 1;
            else start = 0;
            for(int k = start; k <= n-j; k++){
                long long add = power(2,i-1)%mod*comb(n-j,k)%mod*f[i-1+k]%mod;
                sum[i][j] = (sum[i][j]+add)%mod;
            }
        }
    }
}

int p[100005];
int vis[100005];

int find(int u){
    if(p[u]==u) return u;
    else return p[u] = find(p[u]);
}

struct Graph{
    int x,y;
    //for i,j
    int ok;
    Graph(int x=0,int y=0,int ok=0):x(x),y(y),ok(ok){}
};

Graph getGraph(int n){
    Graph res;
    int ok = 1, cycle = 0, node = 0;
    for(int i = 1; i <= n; i++){
        int u = edge[i].u, v = edge[i].v;
        if(!vis[u]) vis[u] = 1, queue[++node] = u;
        if(!vis[v]) vis[v] = 1, queue[++node] = v;
        in[u]++; in[v]++;
        if(in[u]>2) ok = 0;
        if(in[v]>2) ok = 0;
        int x = find(u), y = find(v);
        if(x==y) cycle++;
        p[x] = y;
    }
    if(!ok || cycle>1) res = Graph(0,0,0);
    else if(cycle==1){
        res = Graph(0,0,-1);
        int root = find(queue[1]);
        for(int i = 1; i <= node; i++){
            if(in[queue[i]]!=2) res = Graph(0,0,0);
            int u = find(queue[i]);
            if(u!=root) res = Graph(0,0,0);
        }
    }
    else{
        int seg = 0;
        for(int i = 1; i <= node; i++){
            int u = find(queue[i]), eq = 0;
            for(int j = i+1; j <= node; j++){
                if(find(queue[j])==u) eq = 1;
            }
            if(!eq) seg++;
        }
        res = Graph(seg,node,ok);
    } 
    for(int i = 1; i <= node; i++){
        int u = queue[i];
        in[u] = 0, p[u] = u;
        vis[u] = 0;
    }
    return res;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    preWork(n,m);
    for(int i = 1; i <= m; i++){
        scanf("%d%d",&e[i].u,&e[i].v);
    }
    long long answer = 0;
    for(int i = 3; i <= n; i++){
        long long cur = comb(n,i)*f[i-1]%mod*inv(2)%mod;
        //printf("i = %d, cur = %lld\n",i,cur);
        answer = (answer+cur)%mod;
    }
    //printf("%lld\n",answer);
    long long sign = mod-1;
    for(int i = 1; i <= n; i++) p[i] = i, vis[i] = 0;
    int count = 0;
    for(int i = 1; i < (1<<m); i++){
        int cnt = 0, mask = i;
        for(int j = 1; j <= m; j++){
            if(mask%2) edge[++cnt] = e[j];
            mask /= 2;
        }
        Graph g = getGraph(cnt);
        long long cur = -1;
        if(g.ok==0){ 
            count++;
            cur = 0;
        }
        else if(g.ok==-1){ 
            cur = 1;
        }
        else cur = sum[g.x][g.y];
        if(cnt%2) cur = cur*sign%mod;
        answer = (answer+cur)%mod;
    }
    printf("%lld\n",answer);
    return 0;
}
0