結果

問題 No.1116 Cycles of Dense Graph
ユーザー 37zigen37zigen
提出日時 2020-06-18 15:35:13
言語 Java21
(openjdk 21)
結果
AC  
実行時間 417 ms / 2,000 ms
コード長 7,302 bytes
コンパイル時間 2,719 ms
コンパイル使用メモリ 86,352 KB
実行使用メモリ 62,216 KB
最終ジャッジ日時 2023-09-16 12:07:43
合計ジャッジ時間 11,278 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 89 ms
54,116 KB
testcase_01 AC 217 ms
61,276 KB
testcase_02 AC 105 ms
55,592 KB
testcase_03 AC 100 ms
55,632 KB
testcase_04 AC 127 ms
56,204 KB
testcase_05 AC 172 ms
59,180 KB
testcase_06 AC 186 ms
59,596 KB
testcase_07 AC 134 ms
56,168 KB
testcase_08 AC 125 ms
54,112 KB
testcase_09 AC 134 ms
56,476 KB
testcase_10 AC 133 ms
56,088 KB
testcase_11 AC 180 ms
59,524 KB
testcase_12 AC 166 ms
57,224 KB
testcase_13 AC 124 ms
56,392 KB
testcase_14 AC 132 ms
56,400 KB
testcase_15 AC 133 ms
56,104 KB
testcase_16 AC 163 ms
57,240 KB
testcase_17 AC 124 ms
56,172 KB
testcase_18 AC 132 ms
56,220 KB
testcase_19 AC 163 ms
59,424 KB
testcase_20 AC 181 ms
56,512 KB
testcase_21 AC 212 ms
56,120 KB
testcase_22 AC 252 ms
61,332 KB
testcase_23 AC 147 ms
56,160 KB
testcase_24 AC 417 ms
61,884 KB
testcase_25 AC 127 ms
56,004 KB
testcase_26 AC 342 ms
61,148 KB
testcase_27 AC 131 ms
56,176 KB
testcase_28 AC 206 ms
55,996 KB
testcase_29 AC 124 ms
56,100 KB
testcase_30 AC 80 ms
54,136 KB
testcase_31 AC 79 ms
54,120 KB
testcase_32 AC 80 ms
54,312 KB
testcase_33 AC 78 ms
54,236 KB
testcase_34 AC 79 ms
54,276 KB
testcase_35 AC 77 ms
54,124 KB
testcase_36 AC 355 ms
61,284 KB
testcase_37 AC 309 ms
62,216 KB
testcase_38 AC 350 ms
60,808 KB
testcase_39 AC 266 ms
61,344 KB
testcase_40 AC 281 ms
61,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;

class DJSet {
	int n;
	int[] upper;
	public DJSet(int n) {
		this.n=n;
		upper=new int[n];
		Arrays.fill(upper, -1);
	}
	int root(int x) {
		return upper[x]<0?x:(upper[x]=root(upper[x]));
	}
	boolean equiv(int x,int y) {
		return root(x)==root(y);
	}
	void unite(int x,int y) {
		x=root(x);y=root(y);
		if (x==y) return;
		if (upper[x]<upper[y]) {
			x^=y;y^=x;x^=y;
		}
		upper[y]+=upper[x];
		upper[x]=y;
	}
	int sz(int x) {
		return -upper[root(x)];
	}
	int num() {
		int ret=0;
		for (int i=0;i<n;++i) if (i==root(i) && sz(i)>=2) ++ret;
		return ret;
	}
}

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	final long MOD=998244353;
	final int MAX=100000;
	long[]  fc=new long[MAX];
	long[] ifc=new long[MAX];
	long[] inv=new long[MAX];
	long[]  p2=new long[MAX];
	{
		fc[0]=fc[1]=ifc[0]=ifc[1]=inv[0]=inv[1]=p2[0]=1;
		for (int i=2;i<MAX;++i) {
			fc[i]=i*fc[i-1]%MOD;
			inv[i]=MOD-(MOD/i)*inv[(int)(MOD%i)]%MOD;
			ifc[i]=inv[i]*ifc[i-1]%MOD;
		}
		for (int i=1;i<MAX;++i) {
			p2[i]=2*p2[i-1]%MOD;
		}
	}
	
	long comb(int n,int k) {
		if (n<0||k<0||n-k<0) return 0;
		return fc[n]*ifc[k]%MOD*ifc[n-k]%MOD;
	}
			
	long solve(int N,int[] a,int[] b) {
		int m=a.length;
		int[] x=new int[2*m];
		{
			for (int i=0;i<m;++i) {
				x[2*i]=a[i];
				x[2*i+1]=b[i];
			}
			x=Arrays.stream(x).sorted().distinct().toArray();
			for (int i=0;i<m;++i) {
				a[i]=Arrays.binarySearch(x, a[i]);
				b[i]=Arrays.binarySearch(x, b[i]);
			}
		}
		
		long[][][] dp=new long[3][31][20];
		
		/*		 
		 dp[t][N-n][e]
		 
		 if t=0, e=0
		 if t=1, e=1 and ||P||=1
		 if t=2, otherwise
		*/
		
		for (int i=3;i<=N;++i) {
			dp[0][0][0]+=comb(N,i)*fc[i-1]%MOD*inv[2]%MOD;
			dp[0][0][0]%=MOD;
		}
		{
			int n=N-2;
			for (int i=1;i<=n;++i) {
				dp[1][2][1]+=comb(n,i)*fc[i]%MOD;
				dp[1][2][1]%=MOD;
			}
		}
		
		for (int j=0;j<=30;++j) {
			int n=N-j;
			for (int e=1;e<20;++e) {
				for (int i=0;i<=n;++i) {
					dp[2][j][e]+=fc[e-1]*p2[e-1]%MOD*comb(n,i)%MOD*comb(i+e-1,i)%MOD*fc[i]%MOD;
					dp[2][j][e]%=MOD;
				}
			}
		}
		long ans=0;
		out:for (int s=0;s<1<<m;++s) {
			long parity=Integer.bitCount(s)%2==0?1:(MOD-1);
			DJSet ds=new DJSet(x.length);
			int[] deg=new int[x.length];
			for (int i=0;i<m;++i) if ((s>>i)%2==1) {
				++deg[a[i]];
				++deg[b[i]];
				ds.unite(a[i], b[i]);
			}
			int d1=0,d2=0,c=0;
			for (int i=0;i<x.length;++i) {
				if (deg[i]>=3) continue out;
				if (deg[i]==1) ++d1;
				else if (deg[i]==2)++d2;
			}
			for (int i=0;i<x.length;++i) if (ds.root(i)==i && ds.sz(i)>=2) c+=ds.sz(i);
			if (d1==0 && d2==0) {
				ans=(ans+parity*dp[0][c][0]%MOD)%MOD;
			} else if (d1==0 && ds.num()==1) {
				ans=(ans+parity)%MOD;
			} else if (Integer.bitCount(s)==1) {
				ans=(ans+parity*dp[1][c][1]%MOD)%MOD;
			} else if (d1==2*ds.num()) {
				ans=(ans+parity*dp[2][c][ds.num()]%MOD)%MOD;
			}
		}
		return ans;
	}
	
	long exact(int N,int[] a,int[] b) {
		int M=a.length;
		HashSet<List<Integer>> set=new HashSet<>();
		for (int i=0;i<M;++i) {
			set.add(List.of(a[i],b[i]));
			set.add(List.of(b[i],a[i]));
		}
		class State {
			int vis=0;
			int s,t;
			public State(int s) {
				this.s=s;
				t=s;
				vis|=1<<s;
			}
			State copy() {
				State state=new State(-1);
				state.s=s;
				state.t=t;
				state.vis=vis;
				return state;
			}
		}
		ArrayDeque<State> dq=new ArrayDeque<>();
		for (int i=0;i<N;++i) {
			dq.add(new State(i));
		}
		int[] ans=new int[15];
		while (!dq.isEmpty()) {
			State s=dq.pollFirst();
			for (int dst=0;dst<N;++dst) {
				if (dst!=s.s && (s.vis>>dst)%2==1) continue;
				if (set.contains(List.of(s.t,dst))) continue;
				State next=s.copy();
				if (dst==s.s) {
					ans[Integer.bitCount(s.vis)]++;
				} else {
					next.t=dst;
					next.vis|=1<<dst;
					dq.addLast(next);
				}
			}
		}
		long ret=0;
		for (int i=3;i<ans.length;++i) {
			assert(ans[i]%(2*i)==0);
			ret+=ans[i]/(2*i);
			ret%=MOD;
		}
		return ret;
	}
	
	
	void gen() {
		PrintWriter pw=new PrintWriter(System.out);
		Random rnd=new Random();
		int N=rnd.nextInt(1000)+1;
		int M;
		do {
			M=1+rnd.nextInt(15);
		} while (N*(N-1)/2<M);
		pw.println(N+" "+M);
		int[] as=new int[M];
		int[] bs=new int[M];
		HashSet<List<Integer>> set=new HashSet<>();
		for (int i=0;i<M;++i) {
			int a,b;
			do {
				a=rnd.nextInt(N);
				b=rnd.nextInt(N);
			} while (a==b || set.contains(List.of(a,b)));
			set.add(List.of(a,b));
			set.add(List.of(b,a));
			as[i]=a;
			bs[i]=b;
			pw.println(as[i]+" "+bs[i]);
		}
		pw.flush();
//		long ans0=exact(N, as, bs);
//		long ans1=solve(N,as,bs);
//		assert(ans0==ans1);
//		System.out.println(ans0);
	}
	
	void run() {
//		gen();
		FastScanner sc=new FastScanner();
		int N=sc.nextInt();
		int M=sc.nextInt();
		int[] a=new int[M];
		int[] b=new int[M];
		for (int i=0;i<M;++i) {
			a[i]=sc.nextInt();
			b[i]=sc.nextInt();
			--a[i];--b[i];
		}
		System.out.println(solve(N,a,b));
	}

	void tr(Object...o) {System.out.println(Arrays.deepToString(o));}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
        	ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    
    public double nextDouble() { return Double.parseDouble(next());}
}
0