結果

問題 No.1116 Cycles of Dense Graph
ユーザー DriceDrice
提出日時 2020-07-18 16:10:19
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 157 ms / 2,000 ms
コード長 3,665 bytes
コンパイル時間 1,691 ms
コンパイル使用メモリ 35,920 KB
実行使用メモリ 5,396 KB
最終ジャッジ日時 2023-08-20 13:52:33
合計ジャッジ時間 4,761 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,124 KB
testcase_01 AC 14 ms
4,976 KB
testcase_02 AC 3 ms
5,096 KB
testcase_03 AC 3 ms
5,068 KB
testcase_04 AC 3 ms
4,988 KB
testcase_05 AC 6 ms
5,016 KB
testcase_06 AC 8 ms
5,084 KB
testcase_07 AC 3 ms
4,992 KB
testcase_08 AC 3 ms
5,052 KB
testcase_09 AC 4 ms
5,068 KB
testcase_10 AC 3 ms
5,008 KB
testcase_11 AC 8 ms
4,964 KB
testcase_12 AC 5 ms
4,960 KB
testcase_13 AC 3 ms
5,168 KB
testcase_14 AC 3 ms
4,944 KB
testcase_15 AC 4 ms
5,004 KB
testcase_16 AC 6 ms
5,120 KB
testcase_17 AC 3 ms
5,044 KB
testcase_18 AC 4 ms
4,996 KB
testcase_19 AC 4 ms
5,052 KB
testcase_20 AC 14 ms
5,104 KB
testcase_21 AC 9 ms
5,248 KB
testcase_22 AC 39 ms
5,240 KB
testcase_23 AC 4 ms
5,100 KB
testcase_24 AC 85 ms
5,220 KB
testcase_25 AC 3 ms
5,080 KB
testcase_26 AC 95 ms
5,356 KB
testcase_27 AC 3 ms
5,080 KB
testcase_28 AC 14 ms
5,260 KB
testcase_29 AC 3 ms
5,120 KB
testcase_30 AC 3 ms
5,052 KB
testcase_31 AC 3 ms
5,040 KB
testcase_32 AC 2 ms
4,996 KB
testcase_33 AC 2 ms
4,960 KB
testcase_34 AC 2 ms
5,096 KB
testcase_35 AC 3 ms
5,084 KB
testcase_36 AC 157 ms
5,396 KB
testcase_37 AC 97 ms
5,176 KB
testcase_38 AC 97 ms
5,276 KB
testcase_39 AC 23 ms
5,032 KB
testcase_40 AC 23 ms
5,080 KB
権限があれば一括ダウンロードができます

ソースコード

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