B

思路:第一,我们知道,想要每个涂黑整个图,每行每列都至少要有一个格子被涂黑即每行每列都在一个联通块中,同时至少要涂上n+m-1个,接着一个并查集维护即可

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
//team: lots of balloons
//author: TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=3e5+7;;
const double pi=acos(-1);
using namespace std;
int _,n,m;
vector<pair<int ,int > > vec[100005];
ll a,b,c,d,p;
ll ans;
int fa[maxn];
void init()
{
int hang,lie;

for(int i=1;i<=n*m;i++)
{
fa[i]=i;
a=(a*a*b+a*c+d)%p;
hang = (i-1)/m+1;
lie= (i-1)%m+1+n;//加个别的值让它表示其他节点,不能和行重复了
vec[a].push_back(make_pair( hang , lie));
}
}
int find(int a){//找父节点的同时路径压缩
if(a == fa[a]) return a;
return fa[a] = find(fa[a]);
}
void merge(int x, int y){//合并
fa[find(x)] = find(y);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>a>>b>>c>>d>>p;
init();
for(int i = 0; i <= p; i++){
for(auto j : vec[i]){//并查集
int x = find(j.first);
int y = find(j.second);
if(x != y){
ans += i;
merge(x, y);
}
}
}
cout<<ans<<endl;
return 0;
}

J

思路:三角形三条边的颜色非0即1,那么只有两种情况,三边同色或者两边同色另一边异色,对于后者,我们找到异色角,每个三角形有两个,而异色角的数量对于每个节点而言就是num0 * num1,但是每个异色三角形都被计算了两次,在计算答案的时候需要除以二。又由于是完全图,完全图里面找三元环,三元环总数不难知道是n* (n-1) *(n-2)/6,如此一来对每个节点进行枚举就好,复杂度就从三次方降到了两次方。

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
//team: lots of balloons
//author: TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
namespace GenHelper
{
unsigned z1,z2,z3,z4,b,u;
unsigned get()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
bool read() {
while (!u) u = get();
bool res = u & 1;
u >>= 1; return res;
}
void srand(int x)
{
z1=x;
z2=(~x)^0x233333333U;
z3=x^0x1234598766U;
z4=(~x)+51;
u = 0;
}
}
using namespace GenHelper;
using namespace std;
bool edge[8005][8005];
ll tot,sum;
ll yi ,ling ;
int main() {
int n, seed;
int ans=0;
cin >> n >> seed;
//n=10;
//seed=114514;
srand(seed);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
edge[i][j] = edge[j][i]=read();
//cout<<i <<" "<<j<<" "<<edge[i][j]<<endl;
}

sum=0;
tot=n*(n-1);
tot*=n-2;
tot/=6;
//tot=(n)*(n-1)*(n-2)/6;
for(int i = 0;i<n;i++)
{
ling = yi = 0;
for(int j=0;j<n;j++)
{
if(i==j)
{
continue;
}
if(edge[i][j])
{
yi++;
}
else
{
ling++;
}
}
sum+=yi*ling;
}
cout<<tot-sum/2<<endl;
return 0;
}

经此一役,瓜分牛币的队伍少了我。