結果
問題 | No.1116 Cycles of Dense Graph |
ユーザー | LayCurse |
提出日時 | 2020-07-17 23:16:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 16,388 bytes |
コンパイル時間 | 3,032 ms |
コンパイル使用メモリ | 223,448 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-11-30 02:55:57 |
合計ジャッジ時間 | 19,794 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,496 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 3 ms
10,496 KB |
testcase_05 | AC | 29 ms
5,248 KB |
testcase_06 | AC | 120 ms
5,248 KB |
testcase_07 | WA | - |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 3 ms
5,248 KB |
testcase_10 | AC | 4 ms
5,248 KB |
testcase_11 | AC | 91 ms
5,248 KB |
testcase_12 | WA | - |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | WA | - |
testcase_15 | AC | 4 ms
5,248 KB |
testcase_16 | AC | 22 ms
5,248 KB |
testcase_17 | WA | - |
testcase_18 | AC | 6 ms
5,248 KB |
testcase_19 | WA | - |
testcase_20 | AC | 36 ms
5,248 KB |
testcase_21 | AC | 6 ms
5,248 KB |
testcase_22 | AC | 759 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | TLE | - |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | TLE | - |
testcase_27 | AC | 3 ms
5,248 KB |
testcase_28 | AC | 15 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | WA | - |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 2 ms
5,248 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | TLE | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | AC | 970 ms
5,248 KB |
testcase_40 | WA | - |
ソースコード
#pragma GCC optimize ("Ofast") #include<bits/stdc++.h> using namespace std; #define MD (998244353U) void *wmem; char memarr[96000000]; template<class S, class T> inline S min_L(S a,T b){ return a<=b?a:b; } template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } struct Modint{ unsigned val; Modint(){ val=0; } Modint(int a){ val = ord(a); } Modint(unsigned a){ val = ord(a); } Modint(long long a){ val = ord(a); } Modint(unsigned long long a){ val = ord(a); } inline unsigned ord(unsigned a){ return a%MD; } inline unsigned ord(int a){ a %= (int)MD; if(a < 0){ a += MD; } return a; } inline unsigned ord(unsigned long long a){ return a%MD; } inline unsigned ord(long long a){ a %= (int)MD; if(a < 0){ a += MD; } return a; } inline unsigned get(){ return val; } inline Modint &operator+=(Modint a){ val += a.val; if(val >= MD){ val -= MD; } return *this; } inline Modint &operator-=(Modint a){ if(val < a.val){ val = val + MD - a.val; } else{ val -= a.val; } return *this; } inline Modint &operator*=(Modint a){ val = ((unsigned long long)val*a.val)%MD; return *this; } inline Modint &operator/=(Modint a){ return *this *= a.inverse(); } inline Modint operator+(Modint a){ return Modint(*this)+=a; } inline Modint operator-(Modint a){ return Modint(*this)-=a; } inline Modint operator*(Modint a){ return Modint(*this)*=a; } inline Modint operator/(Modint a){ return Modint(*this)/=a; } inline Modint operator+(int a){ return Modint(*this)+=Modint(a); } inline Modint operator-(int a){ return Modint(*this)-=Modint(a); } inline Modint operator*(int a){ return Modint(*this)*=Modint(a); } inline Modint operator/(int a){ return Modint(*this)/=Modint(a); } inline Modint operator+(long long a){ return Modint(*this)+=Modint(a); } inline Modint operator-(long long a){ return Modint(*this)-=Modint(a); } inline Modint operator*(long long a){ return Modint(*this)*=Modint(a); } inline Modint operator/(long long a){ return Modint(*this)/=Modint(a); } inline Modint operator-(void){ Modint res; if(val){ res.val=MD-val; } else{ res.val=0; } return res; } inline operator bool(void){ return val!=0; } inline operator int(void){ return get(); } inline operator long long(void){ return get(); } inline Modint inverse(){ int a = val; int b = MD; int u = 1; int v = 0; int t; Modint res; while(b){ t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if(u < 0){ u += MD; } res.val = u; return res; } inline Modint pw(unsigned long long b){ Modint a(*this); Modint res; res.val = 1; while(b){ if(b&1){ res *= a; } b >>= 1; a *= a; } return res; } inline bool operator==(int a){ return ord(a)==val; } inline bool operator!=(int a){ return ord(a)!=val; } } ; inline Modint operator+(int a, Modint b){ return Modint(a)+=b; } inline Modint operator-(int a, Modint b){ return Modint(a)-=b; } inline Modint operator*(int a, Modint b){ return Modint(a)*=b; } inline Modint operator/(int a, Modint b){ return Modint(a)/=b; } inline Modint operator+(long long a, Modint b){ return Modint(a)+=b; } inline Modint operator-(long long a, Modint b){ return Modint(a)-=b; } inline Modint operator*(long long a, Modint b){ return Modint(a)*=b; } inline Modint operator/(long long a, Modint b){ return Modint(a)/=b; } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(Modint x){ int i; i = (int)x; wt_L(i); } template<class T, class S> inline T pow_L(T a, S b){ T res = 1; res = 1; for(;;){ if(b&1){ res *= a; } b >>= 1; if(b==0){ break; } a *= a; } return res; } inline double pow_L(double a, double b){ return pow(a,b); } template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } a[k] = aval; } template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } a[k] = aval; b[k] = bval; } template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; } template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } for(i=sz-1;i>k;i--){ d[i] = d[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; d[k] = dval; } template<class S, class T> inline S chmax(S &a, T b){ if(a<b){ a=b; } return a; } template<class T> struct Comb{ int mem_fact; T *factri; T *ifactri; Comb(){ mem_fact = 0; } inline void expand_fact(int k){ if(k <= mem_fact){ return; } chmax(k, 2* mem_fact); if(mem_fact == 0){ int i; factri = (T*)malloc(k * sizeof(T)); ifactri = (T*)malloc(k * sizeof(T)); factri[0] = 1; for(i=(1);i<(k);i++){ factri[i] = i * factri[i-1]; } ifactri[k-1] = 1 / factri[k-1]; for(i=(k-1)-1;i>=(0);i--){ ifactri[i] = (i+1) * ifactri[i+1]; } } else{ int i; factri = (T*)realloc(factri, k * sizeof(T)); ifactri = (T*)realloc(ifactri, k * sizeof(T)); for(i=(mem_fact);i<(k);i++){ factri[i] = i * factri[i-1]; } ifactri[k-1] = 1 / factri[k-1]; for(i=(k-1)-1;i>=(mem_fact);i--){ ifactri[i] = (i+1) * ifactri[i+1]; } } mem_fact = k; } inline T fac(int k){ if(mem_fact < k+1){ expand_fact(k+1); } return factri[k]; } inline T ifac(int k){ if(mem_fact < k+1){ expand_fact(k+1); } return ifactri[k]; } inline T C(int a, int b){ if(b < 0 || b > a){ return 0; } if(mem_fact < a+1){ expand_fact(a+1); } return factri[a] * ifactri[b] * ifactri[a-b]; } inline T P(int a, int b){ if(b < 0 || b > a){ return 0; } if(mem_fact < a+1){ expand_fact(a+1); } return factri[a] * ifactri[a-b]; } inline T H(int a, int b){ if(a==0 && b==0){ return 1; } if(a <= 0 || b < 0){ return 0; } if(mem_fact < a+b){ expand_fact(a+b); } return C(a+b-1, b); } inline T Multinomial(int sz, int a[]){ int i; int s = 0; T res; for(i=(0);i<(sz);i++){ s += a[i]; } if(mem_fact < s+1){ expand_fact(s+1); } res = factri[s]; for(i=(0);i<(sz);i++){ res *= ifactri[a[i]]; } return 1; } inline T Multinomial(int a){ return 1; } inline T Multinomial(int a, int b){ if(mem_fact < a+b+1){ expand_fact(a+b+1); } return factri[a+b] * ifactri[a] * ifactri[b]; } inline T Multinomial(int a, int b, int c){ if(mem_fact < a+b+c+1){ expand_fact(a+b+c+1); } return factri[a+b+c] * ifactri[a] * ifactri[b] * ifactri[c]; } inline T Multinomial(int a, int b, int c, int d){ if(mem_fact < a+b+c+d+1){ expand_fact(a+b+c+d+1); } return factri[a+b+c+d] * ifactri[a] * ifactri[b] * ifactri[c] * ifactri[d]; } inline T Catalan(int n){ if(n < 0){ return 0; } if(mem_fact < 2*n+1){ expand_fact(2*n+1); } return factri[2*n] * ifactri[n] * ifactri[n+1]; } inline T C_s(long long a, long long b){ long long i; T res; if(b < 0 || b > a){ return 0; } if(b > a - b){ b = a - b; } res = 1; for(i=(0);i<(b);i++){ res *= a - i; res /= i + 1; } return res; } inline T P_s(long long a, long long b){ long long i; T res; if(b < 0 || b > a){ return 0; } res = 1; for(i=(0);i<(b);i++){ res *= a - i; } return res; } inline T per_s(long long n, long long k){ T d; int m; if(n < 0 || k < 0){ return 0; } if(n == k && k == 0){ return 1; } if(n == 0 || k == 0){ return 0; } if(k==1){ return 1; } if(k==2){ d = n / 2; return d; } if(k==3){ d = (n-1) / 6; m = (n-1) % 6; if(m==0){ return 3 * d * d + d; } if(m==1){ return 3 * d * d + 2 * d; } if(m==2){ return 3 * d * d + 3 * d + 1; } if(m==3){ return 3 * d * d + 4 * d + 1; } if(m==4){ return 3 * d * d + 5 * d + 2; } if(m==5){ return 3 * d * d + 6 * d + 3; } } assert(0 && "per_s should be k <= 3"); return -1; } } ; struct unionFind{ int *d; int N; int M; inline void malloc(const int n){ d = (int*)std::malloc(n*sizeof(int)); M = n; } inline void malloc(const int n, const int fg){ d = (int*)std::malloc(n*sizeof(int)); M = n; if(fg){ init(n); } } inline void free(void){ std::free(d); } inline void walloc(const int n, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; } inline void walloc(const int n, const int fg, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; if(fg){ init(n); } } inline void init(const int n){ int i; N = n; for(i=(0);i<(n);i++){ d[i] = -1; } } inline void init(void){ init(M); } inline int get(int a){ int t = a; int k; while(d[t]>=0){ t=d[t]; } while(d[a]>=0){ k=d[a]; d[a]=t; a=k; } return a; } inline int connect(int a, int b){ if(d[a]>=0){ a=get(a); } if(d[b]>=0){ b=get(b); } if(a==b){ return 0; } if(d[a] < d[b]){ d[a] += d[b]; d[b] = a; } else{ d[b] += d[a]; d[a] = b; } return 1; } inline int operator()(int a){ return get(a); } inline int operator()(int a, int b){ return connect(a,b); } inline int& operator[](const int a){ return d[a]; } inline int size(int a){ a = get(a); return -d[a]; } inline int sizeList(int res[]){ int i; int sz=0; for(i=(0);i<(N);i++){ if(d[i]<0){ res[sz++] = -d[i]; } } return sz; } } ; template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){ int i; int k = 0; pair<T,int> *r; walloc1d(&r, n, &mem); for(i=(0);i<(n);i++){ r[i].first = arr[i]; r[i].second = i; } sort(r, r+n); if(res != NULL){ for(i=(0);i<(n);i++){ if(i && r[i].first != r[i-1].first){ k++; } res[r[i].second] = k; } } else{ for(i=(0);i<(n);i++){ if(i && r[i].first != r[i-1].first){ k++; } arr[r[i].second] = k; } } return k+1; } template<class T> int coordcomp_L(int n1, T arr1[], int n2, T arr2[], int res1[] = NULL, int res2[] = NULL, void *mem = wmem){ int i; int k = 0; pair<T,int> *r; walloc1d(&r, n1+n2, &mem); for(i=(0);i<(n1);i++){ r[i].first = arr1[i]; r[i].second = i; } for(i=(0);i<(n2);i++){ r[n1+i].first = arr2[i]; r[n1+i].second = n1+i; } sort(r, r+n1+n2); for(i=(0);i<(n1+n2);i++){ if(i && r[i].first != r[i-1].first){ k++; } if(r[i].second < n1){ if(res1!=NULL){ res1[r[i].second] = k; } else{ arr1[r[i].second] = k; } } else{ if(res2!=NULL){ res2[r[i].second-n1] = k; } else{ arr2[r[i].second-n1] = k; } } } return k+1; } int N; int M; int A[20]; int B[20]; int deg[30]; Modint dp[100000+1]; Comb<Modint> c; unionFind uf; Modint solve(int N, int M, int A[], int B[]){ int i; int j; int k; int mx =min_L(30, N); int x = 0; int y = 0; int cnt = 0; Modint res = 0; uf.init(mx); for(k=(0);k<(M);k++){ if(!uf(A[k],B[k])){ cnt++; } } for(k=(0);k<(mx);k++){ deg[k] = 0; } for(k=(0);k<(M);k++){ deg[A[k]]++; deg[B[k]]++; } for(k=(0);k<(mx);k++){ if(deg[k] >= 3){ return 0; } } for(k=(0);k<(mx);k++){ if(deg[k]==1){ x++; } } for(k=(0);k<(mx);k++){ if(deg[k]==2){ y++; } } if(cnt==1 && x==0){ return 1; } if(cnt){ return 0; } x /= 2; N -= x + y; if(x==1){ res += N-1; } if(x==2){ res += 2; } for(i=(3);i<(N+1);i++){ res += c.C(N-x,i-x) * ((pow_L((Modint(2)),x))) * c.fac(i-1) / 2; } return res; } int main(){ int mask; wmem = memarr; int m; int a[20]; int b[20]; Modint res = 0; rd(N); rd(M); { int APIVbQlN; for(APIVbQlN=(0);APIVbQlN<(M);APIVbQlN++){ rd(A[APIVbQlN]); rd(B[APIVbQlN]); } } coordcomp_L(M,A,M,B); uf.malloc(30); for(mask=(0);mask<(1<<M);mask++){ int i; m = 0; for(i=(0);i<(M);i++){ if(((mask) &(1<<(i)))){ arrInsert(m,m,a,A[i],b,B[i]); } } if(m%2){ res -=solve(N, m, a, b); } else{ res +=solve(N, m, a, b); } } wt_L(res); wt_L('\n'); return 0; } // cLay varsion 20200509-1 // --- original code --- // #define MD 998244353 // int N, M, A[20], B[20]; // int deg[30]; // Modint dp[1d5+1]; // Comb<Modint> c; // unionFind uf; // // Modint solve(int N, int M, int A[], int B[]){ // int i, j, k, mx = min(30, N), x = 0, y = 0, cnt = 0; // Modint res = 0; // // uf.init(mx); // rep(k,M) if(!uf(A[k],B[k])) cnt++; // // rep(k,mx) deg[k] = 0; // rep(k,M) deg[A[k]]++, deg[B[k]]++; // // rep(k,mx) if(deg[k] >= 3) return 0; // rep(k,mx) if(deg[k]==1) x++; // rep(k,mx) if(deg[k]==2) y++; // // if(cnt==1 && x==0) return 1; // if(cnt) return 0; // // x /= 2; // N -= x + y; // // if(x==1) res += N-1; // if(x==2) res += 2; // rep(i,3,N+1) res += c.C(N-x,i-x) * ((Modint(2)) ** x) * c.fac(i-1) / 2; // return res; // } // // { // int m, a[20], b[20]; // Modint res = 0; // rd(N,M,(A,B)(M)); // coordcomp(M,A,M,B); // uf.malloc(30); // // rep(mask,1<<M){ // m = 0; // rep(i,M) if(BIT_ith(mask,i)) arrInsert(m,m,a,A[i],b,B[i]); // res if[m%2, -=, +=] solve(N, m, a, b); // } // // wt(res); // }