A 构造

B 联通性

C 莫比乌斯反演

D 图论

E dp

F 网络流

A 构造

按照窗口一样的构造即可满足.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;

ll n,m,w,h;
int main()
{
read(n),read(m),read(w),read(h);
for(int i=1;i<=n-h;i++)
{
for(int j=1;j<=m-w;j++)
cout<<"1";
for(int j=m-w+1;j<=m;j++)
cout<<"0";
cout<<endl;
}
for(int i=n-h+1;i<=n;i++)
{
for(int j=1;j<=m-w;j++)
cout<<"0";
for(int j=m-w+1;j<=m;j++)
cout<<"1";
cout<<endl;
}
}

B 联通性

考虑每个起点都作为无向图上一个点,等价就连起来,然后答案就是联通块个数.

考虑如何连边,首先如果两个点之后的$K$个点都已经是递增的,那么这两个点显然等价,我们把所有的这样的起点先按照环一样去连起来.(等价有传递性,我们不需要连成完全图,因此这里边数是$O(N)$的.)

然后考虑如果不是递增的情况,那么两个点等价当且仅当区间重合,而且等价关系有传递性.并且不存在两个点不相邻但等价并且两个点之间有点不和它们联通(这里的等价关系有归纳性).因此我们判断$i,i+1$这样的点是否等价即可.

综上,连边数量不超过$O(N)$个,$dfs$或使用并查集维护连通块个数即可.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
typedef pair<ll,ll> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
const int maxn=200000;
ll N,K,ans;
vector<ll> P;
set<ll> se;
vector<ll> G[maxn];
void addedge(ll x,ll y)
{
G[x].push_back(y);G[y].push_back(x);
}
ll vis[maxn];
void dfs(int u)
{
vis[u]=1;
for(auto v:G[u])
{
if(!vis[v])
dfs(v);
}
}
vector<ll> eq;
int main()
{
memset(vis,0,sizeof(vis));
read(N);read(K);P.reserve(N+1);
for(ll i=0;i<N;i++) read(P[i]);
ans=0;
int cnt=1;
for(int i=1;i<N;i++)
{
if(P[i]>P[i-1]) cnt++;
else cnt=1;
if(cnt==K) {eq.push_back(i-K+1);cnt=K-1;}
}
for(int i=1;i<eq.size();i++){
addedge(eq[i],eq[i-1]);
}
for(int i=0;i<=K-1;i++)se.insert(P[i]);
for(int i=1;i<=N-K;i++)
{
bool ok=false;
if(P[i-1]==*(se.begin())) ok=true;
// cout<<i<<" "<<ok<<endl;
se.erase(P[i-1]);
se.insert(P[i+K-1]);
// for(auto p:se) cout<<p<<" ";
// cout<<endl;
if(P[i+K-1]==*(--se.end())&&ok)
addedge(i,i-1);
}
for(int i=0;i<=N-K;i++)
{
if(!vis[i])
{
dfs(i);
ans++;
}
}
cout<<ans;
}

C 莫比乌斯反演

记$max$为$\max{A_i}$,推式子:
$$
\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(A_i,A_j)=\sum_{d=1}^{max}1/d\sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_j[(A_i,A_j)==d]
$$
这里来一发莫比乌斯反演:
$$
原式=\sum_{d=1}^{max}1/d\sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_j[(A_i/d,A_j/d)==1]=\sum_{d=1}^{max}1/d\sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_j\sum_{T|(A_i/d,A_j/d)}\mu(T)
$$
考虑枚举$\mu$的值:
$$
原式=\sum_{d=1}^{max}1/d\sum_{T=1}^{max/d}\mu(T)\sum_{i=1}^n\sum_{j=1}^nA_iA_j[Td|A_i ,A_j]
$$
前面发现了经典的迪利克雷卷积的形式,我们可以考虑枚举$Td$,那么可以得到:
$$
原式=\sum_{x=1}^{max}\frac{1}{id}*\mu(x)\sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_j[x|A_i,A_j]
$$
其中:乘积符号表示迪利克雷卷积.前面的卷积的值可以$O(nlogn)$的预处理,后面的式子再搞一下:
$$
\sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_j[x|A_i,A_j]=(\sum_{i=1}^{n}A_i[x|A_i])^2
$$
这里也可以按照值域预处理出来,复杂度则是调和级数的$O(nlogn)$.

那么原题要求的东西就把对角线减掉再除以2即可.

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
/*
* @Author: RBQRBQ
* @Date: 2020-04-15 20:54:51
* @LastEditors: RBQRBQ
* @LastEditTime: 2020-04-15 21:04:25
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const ll maxn=1000005;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
namespace MOD{
inline int M(int x){return (x+20*mod)%mod;}
inline int mul(int x,int y){return 1ll*(M(x))*(M(y))%mod;}
inline int add(int x,int y){return M(x+y);}
inline int sub(int x,int y){return (M(x-y));}
inline int sq(int x){return 1ll*x%mod*x%mod%mod;}}
using namespace MOD;
ll mu[maxn+10],p[maxn+10],phi[maxn+10],v[maxn+10],func[maxn+10],inv[maxn+10];
ll qpow(ll x, ll y) {
if (y == 0) return 1;
ll tmp = qpow(x, y / 2);
if (y % 2 == 0) return 1ll * tmp * tmp % mod;
else return 1ll * tmp * tmp % mod * x % mod;
}
inline void init() {
for(int i=1;i<=maxn;i++)
inv[i]=qpow(i,mod-2);
v[1]=mu[1]=phi[1]=1;
int cnt=0;
for (int i=2;i<=maxn;++i) {
if (!v[i]) p[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for ( int j=1;j<=cnt&&i*p[j]<=maxn;++j) {
v[i*p[j]]=1;
if (i%p[j]) mu[i*p[j]]=-mu[i],phi[i*p[j]]=phi[i]*phi[p[j]];
else { mu[i*p[j]]=0,phi[i*p[j]]=phi[i]*p[j]; break; }
}
}
for(int i=1;i<=maxn;i++)
for(int j=1;j*i<=maxn;j++)
func[i*j]=add(func[i*j],mul(mu[i],inv[j]));
}
int N;
ll A[maxn+10];
ll mp[maxn+10];
ll ans1,ans2;
ll f[maxn+10];
ll mn=-1;

int main(){
read(N);
init();
for(int i=1;i<=N;i++){read(A[i]);ans2=add(ans2,A[i]);++mp[A[i]];mn=max(mn,A[i]);}
for(int i=1;i<=mn;i++)
for(int j=i;j<=mn;j+=i)
{
f[i]=add(f[i],mul(mp[j],j));
}
ans1=0;
for(int i=1;i<=mn;i++)
{
ans1=add(ans1,mul(func[i],sq(f[i])));
}

cout<<(sub(ans1,ans2)*inv[2])%mod;
return 0;
}

D 图论

考虑只有$k=0$的连结情况,满足这些情况的连边方式一定是一个生成森林.

然后考虑把$k=1$的边给加进去.显然在一颗树不能连边;然后这样的话,森林的生成子树里,每棵树都至多有一个待连点.显然能加入的边数最多是每棵树出一个点(有待连点的树出待连点,没有待连点的树任意出一个点),把这些点连成完全图.统计是否 有多余的边.

这样的做法正确性基于这种构造即是能达到的最多边数.首先正确性显然:这样的构造显然满足条件;最优性:如果 多出任意一条边一定使得这条边被加在一棵树内,这是不允许的.

因此小心的分类讨论即可(考虑原图是树的情况;连通块仅有1,2个的情况),用并查集实现即可.

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
/*
* @Author: RBQRBQ
* @Date: 2020-04-17 00:12:29
* @LastEditors: RBQRBQ
* @LastEditTime: 2020-04-18 00:46:34
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
const int maxn =200000;
int f[maxn+10];
int find(int x)
{
if(f[x]==x) return x;
else
{
f[x]=find(f[x]);
return f[x];
}
}
int N;
ll M;
ll Q;
vector<pii> p1;
vector<pii> p2;
signed main()
{
for(int i=0;i<=maxn;i++)
f[i]=i;
read(N),read(M),read(Q);
ll pos=0;
for(int i=1;i<=Q;i++)
{
int x,y,k;
read(x),read(y),read(k);
if(k==0) p1.push_back(make_pair(x,y));else p2.push_back(make_pair(x,y));
if(k==0){
int f1=find(x);
int f2=find(y);
if(f1!=f2) {
pos++;
f[f1]=f2;}
}
}
ll cnt=0;
if(M==N-1)
{
if(p2.size()!=0){
cout<<"No";return 0;}
else {cout<<"Yes";return 0;}
}
for(int i=0;i<N;i++)
if(find(i)==i) cnt++;
ll que=0;
for(auto p:p2)
{
if(find(p.second)==find(p.first))
{
cout<<"No";
return 0;
}
}
if(cnt<=2)
{

if(p2.size()!=0)
{
cout<<"No";
return 0;
}
else
{
cout<<"No";
return 0;
}
}
else
{
ll ans=(1ll*cnt*(cnt-1))/2;

if(((M-1ll*pos)>ans))
{
cout<<"No";
return 0;
}
else
{
cout<<"Yes";
return 0;
}

}
}