gym102222KVertexCovers（高维前缀和，meetinthemiddle）相关的知识介绍及解题思路

1 #include
2 using namespace std;
3 typedef long long ll;
4 typedef unsigned int uint;
5 typedef unsigned long long ull;
6 typedef pair<int,int> PII;
7 typedef pair Pll;
8 typedef vector<int> VI;
9 typedef vector VII;
10 //typedef pairP;
11 #define N 300010
12 #define M 2000010
13 #define fi first
14 #define se second
15 #define MP make_pair
16 #define pb push_back
17 #define pi acos(-1)
18 #define mem(a,b) memset(a,b,sizeof(a))
19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
21 #define lowbit(x) x&(-x)
22 #define Rand (rand()*(1<<16)+rand())
23 #define id(x) ((x)<=B?(x):m-n/(x)+1)
24 #define ls p<<1
25 #define rs p<<1|1
26
27 const //ll MOD=1e9+7,inv2=(MOD+1)/2;
28 double eps=1e-6;
29 int INF=1e9;
30 int dx[4]={-1,1,0,0};
31 int dy[4]={0,0,-1,1};
32
33 ull s[M];
34 ll a[N],f[N];
35
36 int read()
37 {
38 int v=0,f=1;
39 char c=getchar();
40 while(c<48||57if(c==‘-‘) f=-1; c=getchar();}
41 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
42 return v*f;
43 }
44
45 int isok1(int S,int l,int r)
46 {
47 rep(i,l,r)
48 if(!(S>>i&1))
49 {
50 ull now=((s[i]<<(63-r))>>(63-r));
51 if((now&S)!=now) return 0;
52 }
53 return 1;
54 }
55
56 int isok2(int S,int l,int r,int mid)
57 {
58 rep(i,l,r)
59 if(!(S>>i&1))
60 {
61 ll now=(s[i+mid]>>mid);
62 if((now&S)!=now) return 0;
63 }
64 return 1;
65 }
66
67 int main()
68 {
69 int cas=read();
70 rep(v,1,cas)
71 {
72 int n=read(),m=read();
73 ll MOD;
74 scanf("%I64d",&MOD);
75 int mid=n/2;
76 rep(i,0,n-1) scanf("%I64d",&a[i]);
77 mem(s,0);
78 rep(i,1,m)
79 {
80 int x=read(),y=read();
81 x--; y--;
82 s[x]|=1ll<<y;
83 s[y]|=1ll<<x;
84 }
85 int S1=(1<1;
86 rep(i,0,S1) f[i]=0;
87 rep(i,0,S1)
88 {
89 ll t=1;
90 rep(j,0,mid-1)
91 if(i>>j&1) t=t*a[j]%MOD;
92 if(isok1(i,0,mid-1)) f[i]=t;
93 }
94
95 rep(i,0,mid-1)
96 rep(j,0,S1)
97 if(!(j>>i&1)) f[j]=(f[j]+f[j^(1<MOD;
98
99 int S2=(1<<(n-mid))-1;
100 ll ans=0;
101 rep(i,0,S2)
102 {
103 ll t=1;
104 rep(j,0,n-mid-1)
105 if(i>>j&1) t=t*a[j+mid]%MOD;
106 if(isok2(i,0,n-mid-1,mid))
107 {
108 ll base=0;
109 rep(j,0,mid-1)
110 {
111 ull now=(s[j]>>mid);
112 if((now&i)!=now) base|=1<<j;
113 }
114 ans=(ans+t*f[base]%MOD)%MOD;
115 }
116 }
117 printf("Case #%d: ",v);
118 printf("%I64d
",ans);
119 }
120 return 0;
121 }