QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351524#7514. Clique Challengezlc1114RE 2ms4180kbC++178.7kb2024-03-12 00:25:322024-03-12 00:25:32

Judging History

你现在查看的是最新测评结果

  • [2024-03-12 00:25:32]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:4180kb
  • [2024-03-12 00:25:32]
  • 提交

answer

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <sstream>
#include <fstream>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <utility>
#include <cassert>
#include <bitset>
#include <functional>
#include <random>
using namespace std;
#define REP(I,N) for (I=0;I<N;I++)
#define rREP(I,N) for (I=N-1;I>=0;I--)
#define rep(I,S,N) for (I=S;I<N;I++)
#define rrep(I,S,N) for (I=N-1;I>=S;I--)
#define FOR(I,S,N) for (I=S;I<=N;I++)
#define rFOR(I,S,N) for (I=N;I>=S;I--)
#define REP_(I,N) for (int I=0;I<N;I++)
#define rREP_(I,N) for (int I=N-1;I>=0;I--)
#define rep_(I,S,N) for (int I=S;I<N;I++)
#define rrep_(I,S,N) for (int I=N-1;I>=S;I--)
#define FOR_(I,S,N) for (int I=S;I<=N;I++)
#define rFOR_(I,S,N) for (int I=N;I>=S;I--)

#define DEBUG
#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define deputs(str) fprintf(stderr, "%s\n",str)
#else
#define debug(...)
#define deputs(str)
#endif // DEBUG
typedef unsigned long long ULL;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const LL INFF=0x3f3f3f3f3f3f3f3fll;
const LL maxn=1e6+7;
const double pi=acos(-1.0);
const double eps=0.0000000001;
template<typename T>inline T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<typename T>inline void pr2(T x,int k=64) {ll i; REP(i,k) debug("%d",(x>>i)&1); putchar(' ');}
template<typename T>inline void add_(T &A,int B,ll MOD) {A+=B; (A>=MOD) &&(A-=MOD);}
template<typename T>inline void mul_(T &A,ll B,ll MOD) {A=(A*B)%MOD;}
template<typename T>inline void mod_(T &A,ll MOD) {A%=MOD; A+=MOD; A%=MOD;}
template<typename T>inline void max_(T &A,T B) {(A<B) &&(A=B);}
template<typename T>inline void min_(T &A,T B) {(A>B) &&(A=B);}
template<typename T>inline T abs(T a) {return a>0?a:-a;}
template<typename T>inline T fastgcd(T a, T b) {
    int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=min(az,bz),diff; b>>=bz;
    while (a) {
        a>>=az; diff=b-a; az=__builtin_ctz(diff);
        min_(b,a); a=abs(diff);
    }
    return b<<z;
}
int startTime;
void startTimer() {startTime=clock();}
void printTimer() {debug("/--- Time: %ld milliseconds ---/\n",clock()-startTime);}
typedef array<int,4> ar4;
typedef array<int,3> ar3;
std::mt19937 rng(time(0));
std::mt19937_64 rng64(time(0));

const int mod = 1e9+7;
// const int mod=998244353;
// int mod=1;
struct mint {
    long long x;
    mint():x(0) {}
    mint(long long x):x((x%mod+mod)%mod) {}
    // mint(long long x):x(x){}
    mint &fix() { x = (x%mod+mod)%mod; return *this;}
    mint operator-() const { return mint(0) - *this;}
    mint operator~() const { return mint(1) / *this;}
    mint &operator+=(const mint &a) { if ((x+=a.x)>=mod) x-=mod; return *this;}
    mint &operator-=(const mint &a) { if ((x+=mod-a.x)>=mod) x-=mod; return *this;}
    mint &operator*=(const mint &a) { (x*=a.x)%=mod; return *this;}
    mint &operator/=(const mint &a) { (x*=a.pow(mod-2).x)%=mod; return *this;}
    mint operator+(const mint &a)const { return mint(*this) += a;}
    mint operator-(const mint &a)const { return mint(*this) -= a;}
    mint operator*(const mint &a)const { return mint(*this) *= a;}
    mint operator/(const mint &a)const { return mint(*this) /= a;}
    mint pow(long long t) const {
        mint ret=1,cur=x;
        for (; t; t>>=1ll,cur=cur*cur)
            if (t&1) ret=ret*cur;
        return ret;
    }
    bool operator<(const mint &a)const { return x < a.x;}
    bool operator==(const mint &a)const { return x == a.x;}
};

// 0、N比较大的时候可以试试随机shuffle一下贪心选择,或者转化为二分图
// 1、最大团点的数量=补图中最大独立集点的数量
// 2、二分图中,最大独立集+最小点覆盖=整个图的点数量
// 3、二分图中,最小点覆盖=最大匹配
// 4、二分图中,最小边覆盖=最大独立集
// 5、图的染色问题中,最少需要的颜色的数量=最大团点的数量

// 一般图最大团/计数:复杂度可以做到2^(n/2),加剪枝60应该没问题
// CCPC2023网络赛C
// 题意:n=1000; m=1000; 求团个数, 答案mod 1e9+7
// 按度数排一下序, 对于每个团, 枚举团中最小编号的点, 求答案加起来
// 那么团中的每个点向右最多sqrt(2m)条边(因为如果度数为k, 右边每个点度数都>=k)
// 答案加上[i的adj edge的团数量]

// 团和补图独立集是等价的; 求团的数量=求补图独立集数量
// 考虑一个n个点的连通图, 计算最大团个数: 枚举编号最大的点直接暴力复杂度是2^n
// 但是如果记忆化一下2^(n/2),那么复杂度会变成2^(n/2)
// 这里就是枚举一下最大那个u是否被选择过了, dp[S]=dp[S^(1<<u)]+dp[S^(1<<u)^adj[u]];

// 状态数量很多所以这里只能记忆化一部分
// 但是很容易被卡满; 可以加剪枝
// 1.枚举的u度数最大
// 2.如果可以把团分成不相交的两份, 那就直接分成两半去搞然后乘起来

// 最差时间复杂度是, sqrt个点度数是sqrt, 总复杂度sqrt*2^(sqrt/2)=sqrt*1.414^sqrt

struct IndependentSet {  // 点数量<=63
    // 状态压缩一下N; N不要太大否则状态都存不下
    vector<ull> edge,path,cycle;
    IndependentSet(int n=0) { init(n); }
    void init(int n) {
        assert(n<64);
        edge.resize(n);
        path.resize(n+1);
        cycle.resize(n+1);
        path[0]=1; path[1]=2;
        FOR_(i,2,n) path[i]=path[i-1]+path[i-2];
        cycle[0]=1; cycle[1]=2;
        FOR_(i,2,n) cycle[i]=cycle[i-1]+cycle[i-2];
        fill(edge.begin(),edge.end(),0);
    }
    void addedge(int x,int y) {
        assert(max(x,y)<edge.size());
        // printf("addedge %d %d\n",x,y);
        edge[x]|=1ull<<y;
        edge[y]|=1ull<<x;
    }
    void flip() { // 变成补图(团=补图独立集)
        for (ull &e:edge) e^=(1ull<<edge.size())-1;
    }
    ull independent_set(ull S,bool connected=false) {
        // printf("solve %lld ",S);
        // pr2(S,edge.size());
        // puts("");
        // S: 当前存在哪些id set
        if (!S) return 1;
        if (!(S&(S-1))) return 2;
        if (!connected) { // 2.如果可以把团分成不相交的两份, 那就直接分成两半去搞然后乘起来
            ull res=1;
            while (S) {
                int id=__builtin_ctzll(S);
                ull seen=0; // seen:从id能走到的点
                for (ull cur=1ull<<id; cur&~seen;) {
                    int x=__builtin_ctzll(cur&~seen);
                    seen^=1ull<<x;
                    cur|=edge[x]&S;
                }
                res*=independent_set(seen,true);
                S^=seen;
            }
            return res;
        } else {
            int id=-1,degmax=-1,one=0,tot=__builtin_popcountll(S);
            for (ull cur=S; cur;) { // 1.枚举的点度数最大
                int x=__builtin_ctzll(cur),deg=__builtin_popcountll(S&edge[x]);
                if (deg>degmax) degmax=deg,id=x;
                if (deg==1) one++;
                cur^=1ull<<x;
            }
            if (degmax<=2) return one?path[tot]:cycle[tot];
            S^=1ull<<id;
            return independent_set(S)+independent_set(S&~edge[id]);
        }
    }
};

template<typename T>
T count_clique(vector<vector<int>> edge) {
    int n=edge.size();
    vector<int> id(n);
    iota(id.begin(),id.end(),0);  // 0,1,2...
    sort(id.begin(),id.begin()+n,[&](int x,int y) {
        return edge[x].size()<edge[y].size();
    });
    T ans=0;
    vector<int> reid(n,-1); // 给最大团用的
    IndependentSet clique;
    REP_(i,n) {
        int x=id[i],cur_n=0;
        for (int y:edge[x]) if (id[y]>id[x]) reid[y]=cur_n++;
        clique.init(cur_n);
        REP_(y,n) if (reid[y]!=-1)
            for (int z:edge[y]) if (reid[z]!=-1)
                    clique.addedge(reid[y],reid[z]);
        clique.flip();
        ans+=clique.independent_set((1ull<<cur_n)-1);
        for (int y:edge[x]) reid[y]=-1;
    }
    return ans;
}


int solve() {
    int n,m;
    scanf("%d%d",&n,&m);
    vector<vector<int>> edge(n);
    FOR_(i,1,m) {
        int x,y;
        scanf("%d%d",&x,&y);
        x--; y--;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    printf("%lld\n",count_clique<mint>(edge).x);
    return 0;
}
int main() {
    solve();
    // while (1) solve();
}
/*
3 2
1 2
2 3

3 3
1 2
1 3
2 3
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3856kb

input:

3 2
1 2
2 3

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

3 3
1 2
1 3
2 3

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4180kb

input:

1000 100
446 789
167 547
254 777
777 185
33 446
777 847
185 877
757 167
72 383
847 446
254 478
959 185
757 446
847 959
959 167
757 847
747 757
446 167
989 757
547 777
33 747
33 254
254 843
33 547
446 980
877 205
185 72
980 959
33 205
877 757
33 847
478 843
757 478
167 877
72 789
877 959
980 478
167 ...

output:

1373

result:

ok single line: '1373'

Test #4:

score: 0
Accepted
time: 2ms
memory: 4176kb

input:

1000 1000
770 105
219 498
686 498
343 534
15 591
919 588
149 588
298 915
551 523
710 116
105 637
523 991
343 476
145 420
604 588
254 120
551 421
476 298
900 710
915 343
445 421
986 867
445 588
219 356
919 105
584 875
991 604
776 919
588 254
919 421
356 348
105 551
15 113
919 15
356 523
343 155
770 9...

output:

6621319

result:

ok single line: '6621319'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

1000 1000
840 251
559 572
77 993
857 254
176 77
30 423
838 251
862 466
920 254
254 593
593 423
780 575
487 865
952 176
480 77
351 487
620 390
231 496
423 761
993 385
383 390
220 620
862 805
920 838
77 339
838 231
691 384
930 251
840 77
593 993
838 930
176 761
383 761
480 487
251 383
295 390
289 808
...

output:

6403686

result:

ok single line: '6403686'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

1000 1000
179 73
322 80
586 342
73 819
973 184
508 131
351 342
576 179
397 23
523 926
684 73
479 722
973 80
576 397
301 508
903 618
672 192
33 903
973 885
523 661
885 8
787 988
647 990
393 211
722 586
751 926
960 322
179 131
131 988
196 342
508 351
672 342
644 926
990 819
301 80
73 397
104 131
678 3...

output:

6066915

result:

ok single line: '6066915'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3932kb

input:

1000 1000
179 707
71 73
410 726
459 410
84 432
500 73
578 864
71 145
538 578
265 145
707 565
674 772
859 676
826 71
538 459
548 479
609 45
674 707
30 145
45 726
41 73
446 265
145 479
587 642
179 632
908 548
674 410
361 632
500 642
929 976
73 446
41 361
71 726
179 212
341 929
45 859
826 179
632 144
4...

output:

6242289

result:

ok single line: '6242289'

Test #8:

score: 0
Accepted
time: 2ms
memory: 4016kb

input:

1000 1000
146 917
487 589
225 927
972 449
969 728
99 288
615 564
728 146
880 561
563 745
442 880
118 392
634 564
636 917
442 738
280 254
225 710
254 449
221 564
394 969
556 99
634 589
976 301
117 487
561 867
98 880
392 880
917 819
556 634
941 969
653 927
972 615
146 819
969 98
653 941
809 699
590 30...

output:

9171879

result:

ok single line: '9171879'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

1000 1000
709 558
844 316
552 395
944 619
805 279
837 392
822 772
964 805
597 397
814 344
527 401
964 299
922 782
746 349
795 537
945 57
527 176
815 937
257 955
245 108
245 593
932 155
597 812
18 856
116 218
671 142
511 945
481 405
966 695
782 38
130 638
470 692
671 307
837 571
925 43
411 249
613 38...

output:

2186

result:

ok single line: '2186'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

1000 1000
833 350
567 76
488 416
350 135
874 275
555 996
263 152
14 380
409 442
672 836
490 5
421 901
781 875
135 209
162 442
6 47
111 180
317 162
876 368
393 656
712 535
583 976
918 591
29 887
436 599
702 5
512 778
901 111
423 591
274 599
686 655
2 656
444 172
836 800
865 920
3 19
781 375
157 683
8...

output:

2193

result:

ok single line: '2193'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

1000 1000
655 894
253 168
615 321
526 160
225 578
845 473
14 839
321 659
138 448
575 787
342 557
338 501
192 504
888 172
531 616
83 136
623 137
746 344
385 337
505 394
634 740
242 449
321 630
804 971
386 160
466 641
83 133
570 527
448 273
888 653
3 479
467 18
630 93
271 574
653 5
764 370
972 466
501...

output:

2159

result:

ok single line: '2159'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

1000 1000
210 626
59 74
95 486
328 63
894 222
908 764
299 197
871 600
954 241
431 660
816 997
186 34
737 604
889 568
454 115
61 933
417 221
279 971
333 340
143 374
168 409
426 50
875 423
86 413
805 719
222 319
461 864
244 679
49 220
98 579
329 737
568 926
328 330
694 445
318 480
576 748
242 989
968 ...

output:

2013

result:

ok single line: '2013'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3996kb

input:

1000 1000
937 639
771 95
626 134
869 66
465 29
889 944
194 239
284 303
935 111
795 806
737 770
665 343
862 528
232 571
342 458
401 490
452 628
425 384
998 578
192 168
64 651
486 311
840 667
400 255
364 206
486 289
761 912
189 907
158 339
891 336
392 782
598 233
899 539
19 780
190 535
933 700
500 232...

output:

2004

result:

ok single line: '2004'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3980kb

input:

1000 1000
568 607
217 544
12 124
766 801
924 290
957 218
816 552
913 189
982 916
896 289
304 74
426 190
844 543
849 972
386 59
626 472
869 838
234 581
232 707
623 685
873 344
295 496
352 557
314 35
329 432
155 422
803 322
42 735
36 760
249 306
706 533
748 161
887 911
872 64
440 450
662 607
274 659
7...

output:

2002

result:

ok single line: '2002'

Test #15:

score: 0
Accepted
time: 1ms
memory: 4012kb

input:

1000 1000
726 492
65 652
168 218
347 489
35 415
73 324
80 419
237 352
378 3
708 286
933 810
116 563
819 610
670 386
392 940
434 926
341 617
820 842
618 974
592 344
724 578
955 761
26 902
545 496
688 636
273 225
749 840
661 784
917 595
503 84
414 252
925 877
352 479
792 914
54 666
324 257
642 637
801...

output:

2002

result:

ok single line: '2002'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

1000 1000
344 107
264 268
28 38
211 260
741 682
654 885
607 213
610 296
869 556
685 269
996 929
61 370
804 605
786 570
41 448
104 549
245 166
36 84
265 135
704 409
60 299
895 645
868 140
3 483
448 341
778 460
930 13
796 688
936 751
808 458
859 502
918 43
920 287
680 976
918 172
378 156
962 834
635 3...

output:

2002

result:

ok single line: '2002'

Test #17:

score: -100
Runtime Error

input:

1000 1000
117 152
117 375
190 586
117 586
278 546
788 450
117 90
511 586
450 595
586 492
870 278
17 117
586 275
520 471
796 117
520 112
117 431
292 520
320 520
278 95
586 677
450 402
298 520
586 109
450 409
520 607
684 278
520 898
340 278
17 520
586 64
586 100
520 647
450 270
520 617
685 117
117 985...

output:


result: