結果
| 問題 | No.1116 Cycles of Dense Graph |
| ユーザー |
 37zigen
|
| 提出日時 | 2020-06-18 17:49:37 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,648 bytes |
| コンパイル時間 | 2,872 ms |
| コンパイル使用メモリ | 87,056 KB |
| 実行使用メモリ | 60,952 KB |
| 最終ジャッジ日時 | 2024-07-03 12:54:26 |
| 合計ジャッジ時間 | 9,709 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 RE * 10 |
ソースコード
// 制約侵害確認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=0if t=1, e=1 and ||P||=1if 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=1000;//rnd.nextInt(1000)+1;int M=15;// 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();assert(1<=N&&N<=1000);assert(0<=M&&M<=Math.min(15,N*(N-1)/2));int[] a=new int[M];int[] b=new int[M];HashSet<List<Integer>> set=new HashSet<List<Integer>>();for (int i=0;i<M;++i) {a[i]=sc.nextInt();b[i]=sc.nextInt();assert(1<=a[i]&&a[i]<=N&&1<=b[i]&&b[i]<=N);assert(a[i]!=b[i]);assert(!set.contains(List.of(a[i],b[i])));set.add(List.of(a[i],b[i]));set.add(List.of(b[i],a[i]));--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());}}