Codeforces Round 548

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
D(莫反), E(网络流)

D

题目HERE

题目大意

1<=m<=100'000

$ dp[x] =1 + \sum_{j=1}^{m}\frac{dp[gcd(j,x)]}{m} $

求$ans=\sum_{i=1}^{m}\frac{dp[i]}{m}$

上面公式怎么来的呢，一眼可见

解法

我做的时候卡在变形上了

首先，我们观察到右侧的dp中是j与x的gcd，那么也就是取值范围都是 x的约数，那么变形有

$f[n]=1+\sum_{d|n}\frac{f[d]\cdot g(n, d)}{m}$

其中g(n,d)表示 从1到m，和n gcd后结果为d的 数 的个数，也就是

$ g(n, d) = \sum_{i=1}^m[gcd(n, i)=d] $

同时乘上m，并把右侧 的f[n]的部分移到左侧

$(m-\lfloor\frac{m}{n}\rfloor)f[n]=m+\sum_{d|n,d\neq n}f[d]\cdot g(n, d)$

现在问题还有怎么计算g

观察g的表达式，说明i一定是d的倍数，所以可以变成d*?

$ g(n, d) = \sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(n,i*d)=d] $

$ g(n, d) = \sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(\frac{n}{d},i)=1]$

注意到右侧的 求和部分实际是要gcd=1时，返回1，其它情况返回0，这和

$\mu * 1 = \epsilon$对应，也就是莫比乌斯，$\mu$函数 的因子和的性质，详细内容见下方我之前的莫反总结中写到的性质和证明

$\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|gcd(\frac{n}{d},i)}\mu(t)$

$=\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|\frac{n}{d},t|i}\mu(t)$

$=\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac {\lfloor \frac{m}{d} \rfloor} {t} \rfloor$

$=\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac{m}{dt} \rfloor$

综上

$(m-\lfloor\frac{m}{n}\rfloor)f[n]=m+\sum_{d|n,d\neq n}f[d]\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac{m}{dt} \rfloor$

官方题解

官方题解

[题解1]

没有看懂后面的变形，怎么突然1就没了，m的系数移动后也没了??

方法也是讲如何计算g(n,d)，计算多少个p=1->m 使得 gcd(p,n)=d

假设用乘法表示n和p，n=d*a,p=d*b, 有1<=p<=m,gcd(a,b)=1,也就是1<=b<=m/d

然后对a因数分解，因此b不能含有a的任何因子，然后用 容斥算，因为n很小最多6个不同的质因子，所以简单dp

[题解2 就是莫反了]

总结

我之前的莫反总结

参考

CODE 代码很丑见谅XD

E

题目HERE

题目大意

n个人 最大5000

m个组 最大5000

每个人有潜力值最大 5000

每个人仅属于一个组

每一轮删除一个指定的人index_i(输入提供)

一共d轮，最大n

每一轮，从各组中选一个人构成数组，选出后放回原来的组，求每一轮的最大mex

mex:{数组中未出现的最小自然数},如 mex{0,1,2,3,6,7} = 4

解法

先倒转顺序，离线处理，把删除人变为向组中加人

网络流

起始节点到各个组节点建一条边，

各组的人向他的潜力值节点建立边

潜力值0 向end建立边

当潜力值i 连接到end后，总流量等于i+1时(因为从0开始)，把潜力值i+1也连接到end

O(轮数*网络流复杂度) <= O(d*(m+n+mex))

CODE

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

#define ST 0
#define END 10005
#define POT(v) (v+5001)

// 0 ,   1-5000 , 5001-10002 10005
// st->1 -> group->1 -> potential(5001+mex+1) ->1(dynamic add) -> end

// reverse order

map<int,int>flow[10010];

int n,m,d;
int p[10010];
int c[10010];
bool notin[10010];
int order[10010];
int ans[10010];
int mex = 0;
int vis[100010];

int dfs(int i,int load){
  if(i == END)return load;
  vis[i] = true;
  for(auto item:flow[i]){
    if(vis[item.first])continue;
    if(item.second != 0){
      int ret = dfs(item.first,min(load,item.second));
      if(ret != 0){
        flow[i][item.first] -= ret;
        flow[item.first][i] += ret;
        return ret;
      }
    }
  }
  return 0;
}

int getflow(){
  int ret = dfs(ST,1);
  rep(i,0,m+1){
    vis[i]=false;
  }
  rep(i,0,5000){
    vis[POT(i)] = false;
  }
  return ret;
}

int main(){
  cin>>n>>m;
  rep(i,1,n+1){
    scanf("%d",p+i);
  }
  rep(i,1,n+1){
    scanf("%d",c+i);
  }
  scanf("%d",&d);
  rep(i,0,d){
    scanf("%d",order+i);
    notin[order[i]] = true;
  }
  // built
  // ST->group
  rep(i,1,m+1){
    flow[ST][i] = 1;
  }
  // group->mex
  rep(i,1,n+1){
    if(notin[i])continue;
    flow[c[i]][POT(p[i])] = 1;
  }
  // mex 0 -> end
  flow[POT(mex)][END] = 1;
  per(i,0,d){
    while(getflow()){
      flow[POT(++mex)][END] = 1;
    }
    ans[i] = mex;
    // [order]->mex
    flow[c[order[i]]][POT(p[order[i]])]+=1;
  }
  rep(i,0,d){
    printf("%d\n",ans[i]);
  }
  return 0;
}

总结

CODE