【cf985G】Team Players【bzoj5407】girls

Source

cf985G
bzoj5407

Hint

请先思考后再展开

一开始想着按照某种特殊的顺序依次处理每条限制,然后答案减去新产生的非法三元组
那么就是要求【目前x和y都能连的点和】,然后不会维护……或许有人会?
正解是容斥,然后三元环计数类似【Jsoi2017】原力

Solution

请先思考后再展开

$$
\begin{aligned}
& 考虑容斥推系数,ans=f0-f1+f2-f3 \\
& f0=\sum_i i(A*C_{n-i}^2+B*(i-1)(n-i)+C*C_{i-1}^2) \\
& f1,枚举每条边考虑每种情况 \\
& f2的话维护每个点不能去的数量与编号和sm_{0/1}(x)、bg_{0/1}(x),枚举每个点考虑每种情况 \\
& f3,设阈值T,然后度数>T为A类,<=T为B类;如果AAA直接枚举,(\frac{2m}{T})^3 \\
& 否则,枚举一个B,枚举其两条边,注意ABB要/2,BBB要/3,复杂度上界为 mT \\
& T=2\sqrt m时复杂度接近m^{3/2}
\end{aligned}
$$
除f3外都是线性的

还有就是hash的部分,如果用普通的hash不知道是不是我的姿势有点问题只能在bzoj过
然后去CF学习了一下,就是利用A很少的性质处理个bitset,然后为了判BBB,在BB的时候y扫一遍后再扫x即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
ll qread()
{
ll ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) putchar('-'),num=-num;
if(num>=10) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
const int INF=0x3f3f3f3f;
const int MOD=19930726;
void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll invm(ll x){return qpower(x,MOD-2);}
const int N=2e5+10;
typedef unsigned long long ull;
bitset<N> hash[1000];int id[N];vc<ull> AA;bool v[N];
ull GG(ull n){return (n&1)?((n-1)/2*n):(n/2*(n-1));}
ull sm[2][N],bg[2][N];vc<ull> smm[N],bgg[N],go[N];
void writegg(ull num)
{
if(num>=10) writegg(num/10);
putchar('0'+num%10);
}
void main()
{
ull n,m,A,B,C;scanf("%lld%lld%lld%lld%lld",&n,&m,&A,&B,&C);ull ans=0;
for(ull i=0;i<n;i++) ans+=i*(GG(n-1-i)*A+i*(n-1-i)*B+GG(i)*C);
for(ull i=1;i<=m;i++)
{
ull x=qread(),y=qread();if(x>y)swap(x,y);
bg[0][x]++;bg[1][x]+=y;sm[0][y]++;sm[1][y]+=x;
bgg[x].PB(y);smm[y].PB(x);go[x].PB(y);go[y].PB(x);
ull ss=x; ans-=A*GG(ss)+ss*(B*x+C*y);
ull mm=y-x-1;ans-=B*(GG(mm)+(x+1)*mm)+mm*(A*x+C*y);
ull bb=n-y-1;ans-=C*(GG(bb)+(y+1)*bb)+bb*(A*x+B*y);
}
for(ull i=0;i<n;i++)
{
sort(smm[i].begin(),smm[i].end());sort(bgg[i].begin(),bgg[i].end());
ull s=sm[0][i];ans+=GG(s)*C*i;for(ull a=0;a<s;a++)ans+=smm[i][a]*(A*(s-1-a)+B*a);
ull b=bg[0][i];ans+=GG(b)*A*i;for(ull a=0;a<b;a++)ans+=bgg[i][a]*(B*(b-1-a)+C*a);
ans+=s*b*B*i+sm[1][i]*A*b+bg[1][i]*C*s;
}
ull T=2*sqrt(m);
for(ull i=0;i<n;i++) if(sm[0][i]+bg[0][i]>T)
{
AA.PB(i);id[i]=AA.size();
for(int t=0;t<(int)go[i].size();t++) hash[id[i]][go[i][t]]=1;
}
for(int i=0;i<(int)AA.size();i++)for(int j=i+1;j<(int)AA.size();j++)
for(int k=j+1;k<(int)AA.size();k++)ans-=A*AA[i]+B*AA[j]+C*AA[k];
for(ull x=0;x<n;x++) if(!id[x])
{
sort(go[x].begin(),go[x].end());
for(int i=0;i<(int)go[x].size();i++)
{
ull y=go[x][i];
if(!id[y]) for(int j=0;j<(int)go[y].size();j++) v[go[y][j]]=1;
for(int j=i+1;j<(int)go[x].size();j++)
{
ull z=go[x][j];
if(!id[y] and id[z] and (!(x<y) or !hash[id[z]][y]))continue;
if(id[y] and !id[z] and (!(x<z) or !hash[id[y]][z]))continue;
if(!id[y] and !id[z] and (!(z<x) or !v[z]))continue;
if(id[y] and id[z] and !hash[id[y]][z])continue;
if(x<y) ans-=A*x+B*y+C*z;
else if(x<z) ans-=A*y+B*x+C*z;
else ans-=A*y+B*z+C*x;
}
if(!id[y]) for(int j=0;j<(int)go[y].size();j++) v[go[y][j]]=0;
}
}
writegg(ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7f6.html
转载请注明出处,谢谢!