Codeforces Round 796

發表於 更新於 分類於 ， Disqus： 文章字數： 3.7k 所需閱讀時間 ≈ 12 分鐘
D(数学,跳点) E(数学,构造,min-max容斥,kmin/kmax容斥)

D

$f(x) = $比x大的最小平方数

$g(x) = $比x小的最大平方数

如果 $x - g(x) < f(x) - x$ 那么$x$是好的

给长度$n$的单调数组$a$, 求最小非负$k$,使得$a_i+k$ 全为好的

范围

$n \le 10^6$

$a_i \le 2\cdot 10^6$

2s

256MB

题解

我的思路

先做点数学变形

易知对于任意$x=a_i$, 如果$\exists w, x \in [w^2,w^2+w]$ 那么$x$是好的

然后 真不会了

官方

显然 $k \le a_n^2$, 因为 $[a_n^2,a_n^2+a_n]$ 的长度都是 $a_n$ 一定能放下所有数

根据上面的令$f(x) = w$, $w$由$x$唯一得到,也可能不存在, 且有$max(w) \le a_n$,

枚举$f(a_1 + k)$的结果$w_1$, 因为$w_1 \le a_n$ 得到$\le a_n$个初始的$k$取值范围区间

然后枚举 $f(a_i + k)$ 的所有区间

这里有个神奇的地方在于

如果把好的位置用x标出来

1
2
1 2 3 4 5 6 7 8 9 10 11 12
x x   x x x     x  x  x  x

那么选择一个好的完整区间, 向右任意平移, 去取交, 一定只会和一个区间相交, 这样就保证了无论怎么交 都是连续的区间

因此这里假设计算之前$k$的范围是$[min(k),max(k)]$ , 那么计算$[a_i+min(k),a_i+max(k)]$中合法的区间, 而这一定是其中连续的一段, 所以只需要$min,max$两个指针就能维护$k$的取值范围

伪代码

1
2
3
4
5
6
7
8
9
for w_1 = sqrt(a_1)...a[n]: // 枚举w = f(a_1+k)
  krange = [...] // k的可选范围
  for i = 2..n:
    // 注意到 合法与不合法的间隔单调递增, 所以 交完后还是连续区间
    krange = krange 交 calc(krange, a_i)
    if len(krange) == 0:
      break
  if len(krange) > 0:
    return krange.start

这样外层$w_1$范围$O(a_n)$, 每轮内部循环最多$n$次, 总复杂度$O(n a_n)$, 过不了

实际上只需要考虑的是$f(a_i+k) \neq f(a_{i-1} + k)$, 这样的$a_{i-1}$和$a_i$带来的影响

因为如果 $i \in [l,r]$ 都让$f(a_i + k) = w$的话, 那么只有端点$l$和$r$ 会真实的对$k$的区间产生贡献

对于给定的 $f(a_1+k) = w_1$ ,相邻的$f$不等的情况不超过$O(\frac{a_n}{w_1})$种

因为 $a_1+k \in [w_1^2,w_1^2+w_1]$, 所以$a_n+k \in [w_1^2+a_n-a_1,w_1^2+w_1 + a_n-a_1]$

$f(a_n+k) \le \sqrt{w_1^2+w_1 + a_n-a_1} \le \sqrt{(w_1+1)^2 + a_n + (\frac{a_n}{2(w_1+1)})^2} \le w_1+1 + \frac{a_n}{2(w_1+1)}$, 得证

? 有啥简单一点的证明方式吗

所以总复杂度是 $O(\sum_{w_1=\sqrt{a_1}}^{a_n}{\frac{a_n}{w_1}}) = O(a_n log (a_n))$,

代码

https://codeforces.com/contest/1687/submission/159707568

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
ll a[1000010]; // 有序 ai < 2e6

ll mysqrt(ll v){
  ll l = 1;
  ll r = v;
  while(l != r){
    ll mid = (l+r)/2;
    // 先控范围防止 overflow
    if( v/mid < mid ){
      r = mid - 1;
    }else if( mid * mid <= v && (mid+1)*(mid+1) > v){
      return mid;
    }else if( (mid+1) * (mid+1) <= v){
      l = mid + 1;
    }else {
      r = mid - 1;
    }
  }
  return l;
}

// k 的初始范围 [l_k..r_k], 初始f(a_1+k) = w
bool calc(ll w,ll &l,ll &r){
  while(true){
    // [a[i] + l_k, a[i] + r_k] \subset [w^2,w^2+w]
    // 找同为w的最大的j [a[j] + l_k, a[j] + r_k] \subset [w^2,w^2+w]
    // (a[j] + l_k) \in [w^2,w^2+w] 即, a[j] <= w^2+w - l_k
    //                                  r_k <= w^2+w-a[j]
    int idx = lower_bound(a,a+n,w*(w+1)-l+1) - a; // j = idx-1
    r = min(r,w*(w+1) - a[idx-1]); // 更新 r_k <= w^2+w - a[j]
    if(l > r) return false;
    if(idx == n)return true; // 最后一个

    w = mysqrt(a[idx]+r); // 下一个位置的w, (a[idx]+r_k) \in [w_1^2,(w_1+1)^2]
    l = max(l,w*w - a[idx]);
    r = min(r,w*(w+1) - a[idx]);
    if(l > r) return false;
  }
  assert(false);
  return true;
}

int main(){
  n = read();
  rep(i,0,n) a[i] = read();
  // w = f(a_0 + k) = [sqrt(a[0])..a[n-1]]
  rep(w,mysqrt(a[0]),a[n-1]+1){
    // 初始化 k的范围[l..r]
    ll l = max(w*w - a[0],(ll)0);
    ll r = w*(w+1) - a[0];
    if(r < l) continue;
    // 成功的话 k \in [l..r] 都是合法的, l就是要求的最小的
    if(calc(w,l,r)){
      printf("%lld\n",l);
      return 0;
    }
  }
  assert(false);
  return 0;
}

总结

通过枚举$w = f(a_0+k)$来让$k$的取值范围是连续的一段, 且只有$a$的区间端点有影响

完全没想到是通过$w$来划分的, 也就是还是有点按结果划分的感觉,但又不是二分的划分形式

而且这里$w$会让变化次数是$O(\frac{a_n}{w})$ 也是优化的关键点

然后就是这个神奇的刚刚好, 向右平移的交一定是连续区间

参考

官方

E

评分3500,题是国内洛谷大佬出的, t神都炸了

长n的数列a

初始 v = 1

不超过1e5操作,让gcd(all(ai * aj)) = v,i != j, 就是所有不相同的两个数的乘积的gcd

一次操作, 选取a的一个子序列b,(子序列=保持顺序不要求连续)

并执行v = v * lcm(b)或 v = v / lcm(b), 注意的是过程中,v 可以不是整数, 这里是数学除,不是整除

同时保证,所有选取的b的长度和 小于1e6

输出任何一个满足要求的方案

范围

n 1e5

ai 1e6

3s

512MB

题解

我的思路

考虑所有与 a1 乘的

a1 * gcd(a2,...,an)

所有与a2乘的

a2 * gcd(a1,a3,...,an)

但怎么组合并不知道

反过来,既然是gcd/lcm,乘法,那么就考虑质数的出现计数

所有ai的两两相乘的gcd,其实就是 每个质数出现次数, 最小的两个和

所以目标的v 是O(n log ai) 可以得到的

那么问题是如何通过lcm去搞, 题目里说 It can be shown that the answer exists

如果是两个数的gcd

gcd(a,b) * lcm(a,b) = ab

gcd(a,b) = lcm(a,a) * lcm(b,b) / lcm(a,b)

考虑一下小的情况

两个数

v = a0 a1 = lcm(a0,a0) * lcm(a1,a1)

三个数

a0 = k0 q x y

a1 = k1 q y z

a2 = k2 q z x

其中 q = gcd(a0,a1,a2)

gcd(a0,a1) = qy

gcd(a1,a2) = qz

gcd(a2,a0) = qx

那么有 lcm(a0,a1,a2) = k0 k1 k2 q x y z

lcm(a0,a1) = k0 k1 q x y z

lcm(a1,a2) = k1 k2 q x y z

lcm(a2,a0) = k2 k0 q x y z

那么 目标 v = q q x y z

而观察上面的lcm, 注意到如果用一个的, 会出现如果要x y z 相等 那么会造成 q比它们多, 需要使用一个元素

那么 q x y z = lcm0 lcm1 lcm2 / lcm 012

四个数

考虑从三个数变形

a0 = k0 q x y

a1 = k1 q y z

a2 = k2 q z x

a3

目标是 v = gcd(a3 q,q q x y z)

这相当于 v(a0,a1,a2,a3) = gcd(a3 gcd(a0,a1,a2),v(a0,a1,a2))

如果按照这个写法,去看3个数

v(a0,a1,a2) = gcd(a2 gcd(a0,a1), v(a0,a1))

= lcm(a2 gcd(a0,a1) lcm(v(a0,a1)) / lcm(a2 gcd(a0,a1), v(a0,a1))

= v(a0,a1) a2 gcd(a0,a1) / lcm(a2 gcd(a0,a1), v(a0,a1))

= v(a0,a1) lcm(a2) lcm(a0) lcm(a1) / (lcm(a2 gcd(a0,a1), v(a0,a1)) lcm(a0,a1))

= ???

= 0 1 2 / 012

只能说 v(a0,a1) / (lcm(a2 gcd(a0,a1), v(a0,a1) lcm(a0,a1) == lcm(0,1,2) ?

没有什么思路

再会看题目 n是1e5, 但希望操作不要超过1e5

但注意到上面3个数的时候用了4次,

具体例子

a0 = 11 2 3 5

a1 = 13 2 5 7

a2 = 17 2 7 3

lcm(0,1) = 11 13 2 3 5 7

lcm(1,2) = 13 17 2 3 5 7

lcm(2,0) = 17 11 2 3 5 7

lcm(0,1,2) = 11 13 17 2 3 5 7

v(0,1,2) = 2 2 3 5 7 = lcm0 lcm1 lcm2 / lcm012

说明3个的做法对于大的n并不通用, 通用的应该要能达到n个是n次的样子

对于大的n, 不会使用单个, 因为单个会有独立的系数, 任何其它gcd无法消掉

那不如强行拆一下四个数

其中k是独立的部分

1
2
3
4
a0 = k0  b c d        w x y    q
a1 = k1  b     e f    w x   z  q
a2 = k2    c   e   g  w   y z  q
a3 = k3      d   f g    x y z  q

发现其中出现次数都是C(4,i)对应的表现

v = w x y z q q

一个为组的轮换 (1次) (2次) (3次) (4次)

两个为组的轮换 (3次) (5次) (6次) (6次)

三个为组的轮换 (3次) (4次) (4次) (4次)

四个为组的轮换 (1次) (1次) (1次) (1次)

以线性方程组的知识, 显然 (0 0 1 2) = (1 2 3 4) + 2(1 1 1 1) - (3 4 4 4), 次数是 4 + 2 * 1 + 4 要10次

剩下的观察就是, n 1e5, 而 ai 1e6

也就是说可能有不少的因子被干掉了

并不知道如何量化分析了

只知道 k0,k1,k2,k3,b,c,d,e,f,w,x,y,z 应该是两两互质的, 否则把它们的gcd提取出来转到下一级别

而如果全部互质, 那么2*3*5*7*8*11*13 = 240240 在超界的边缘

似乎不可能构成的样子

官方

考虑容斥原理

一样的, 对于一个质数的幂次 在结果中 = 这个质数最小出现的两个幂次的和

广义 容斥

$\gcd_{i\ne j}{A_i\times A_j}=\prod_{T\subseteq U}\text{lcm}(T)^{(-1)^{|T|}(|T|-2)}$

证明一下这个表达式

因为对于不同质数,可以独立的看其幂次

不妨设对于一个具体质数, 它在这些数组元素中的幂次从小到大为 p0 p1 >=p1 >=p1 ..., 也就是a0按照p的幂次排序

需要的是$p_1+p_2$

$(lcm(a_1)) \cdot (lcm(a_2) \cdot lcm(a_1,a_2)^0 ) \cdot ( a_3^{ 1 + 0 + (-1) } \cdot (a4^{ 1 + 0 + (-1 \cdot 3) + 2 \cdot 1}) \cdot (a_5^{1 + 0 + (-1 \cdot 6) + (2 \cdot 4) + (-3 \cdot 1)}) \cdots$

$ = a_1 \cdot a_2 = p^{p_1+p_2}$

这么神奇的吗

你会发现$lcm_k, k \ge 3$ 的幂次为

$ \sum_{i=1}^k (-1)^i \cdot (i-2) \cdot C(k-1,i-1) $

$ = - \sum_{i=0}^{k-1} (-1)^i \cdot (i-1) \cdot C(k-1,i)$

$ = - \sum_{i=0}^{w} (-1)^i \cdot (i-1) \cdot C(w,i) , w = k-1 \ge 2$

$ = - \sum_{i=0}^{w} (-1)^i \cdot i \cdot C(w,i)$ ( 因为$w \ge 2 > 0 时, 0 = (1-1)^w = \sum_{i=0}^{w} (-1)^i \cdot C(w,i)$

$ = - \sum_{i=0}^w (-1)^i \cdot i \cdot \frac{w!}{i!(w-i)!} $

$ = - \sum_{i=1}^w (-1)^i \cdot i \cdot \frac{w!}{i!(w-i)!} $

$ = - \sum_{i=1}^w (-1)^i \cdot \frac{w!}{(i-1)!(w-i)!} $

$ = - w \sum_{i=1}^w (-1)^i \cdot \frac{(w-1)!}{(i-1)!(w-i)!} $

$ = - w \sum_{i=1}^w (-1)^i \cdot C(w-1,i-1) $ ( 同上 因为$w-1 \ge 2-1 > 0 时, 0 = (1-1)^w = \sum_{i=0}^{w} (-1)^i \cdot C(w,i)$

$ = - w \cdot 0$

$ = 0 $

其中 $ k - 1 = w \ge 2$

算强行证明了

题解的过程是 有得到第k小的数的反演公式 $k\text{-th}\min{S}=\sum\limits_{\varnothing\ne T\subseteq S}(-1)^{|T|-k}\tbinom{|T|-1}{k-1}\max{T}$

那么 其实就是最小的(k=1) + 次小的(k=2) 得到

一个可重整数集$S$, 其中整数范围$[1,10^6]$, 那么 总能选出大小不超过7的子集$T\subseteq S$, 让$\gcd(S)=\gcd(T)$

易证,因为$gcd(S) \le 10^6$ 所以它的质因子个数不超过7个, T只需要每个质因子的最小幂次选出来就行了

但和本题还是有区别

本题是 $gcd_2(S)$的情况, 两两下标不同乘积的gcd

这样考虑 先让集合$T$为空, 然后我们针对质数p 的幂次来讲, 假设前面已经选了几轮了, 那么最坏情况, 没有选p的最低和次低幂次, 所以为了让p的幂次满足, 任选两个最低和次低幂次, 也就是填2个, 而这种情况说明$gcd_2(S)$ 至少包含p的一次方

所以 最多有7个不同的有效p,最多选14个就能达成

这样也没要求最小数量

直接用上面的lcm和gcd的min/max 表达式就可以了

因为可能其它数字 虽然贡献是两个0次,但是因为, 只做了幂次最小限制,会让它们的gcd不止是对应的幂次

wa5或者看下面的例子

1
2
3
4
2   3 5 7
2     5
2 2 3
2 2     7

注意到3,5,7的最小两个幂次和都是0,而2的最小两个幂次和为1+1=2

但是如果你只选前两个去做集合运算,那么gcd = 2 5

所以你可以通过数量控制

关于Min-Max 容斥

$max_k(S) = $ 集合$S$的第$k$大元素

TODO 再整理一篇文章: 反演 => 二项式反演 => min-max 反演 => kmax/kmin 反演

代码

感觉代码还真不难写, 纯代码不到100行,毕竟给了3s

https://codeforces.com/contest/1687/submission/159885371

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
#define all(O) O.begin(),O.end()

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
int a[100010];
int v2p[1000010]; // 每个数的质数拆解

const int INF = 0x3f3f3f3f;

int getpwr(int v,int p){
  int r = 0;
  while(v % p == 0){
    r++;
    v/=p;
  }
  return r;
}

int main(){

  int n = read();
  rep(i,1,n+1) a[i] = read();

  // 质数 到最低两个幂次 和对应的数的下标
  unordered_map<int, vector< pair<int,int> > > p2low2;
  // 质数
  rep(i,2, 1000000){
    if(v2p[i])continue; // 合数
    p2low2[i] = vector(2,make_pair(INF,-1));
    for(ll j = i*i;j <= 1000000;j+=i){
      v2p[j] = i;
    }
  }

  // 筛出至多14个数
  rep(i,1,n+1) {
    vector<int> rm;
    for(auto &item: p2low2){
      auto &[p,low2] = item;
      low2.push_back({getpwr(a[i],p),i});
      sort(all(low2));
      low2.pop_back();
      if(low2.back().first == 0 && p2low2.size() >= 7 + 1 + rm.size()){ // wa5, 0 幂次贡献也有作用
        rm.push_back(p);
      }
    }
    for(auto p:rm) p2low2.erase(p);
  }

  vector<int> pos;
  for(auto &[p,low2]:p2low2){
    pos.push_back(low2[0].second);
    pos.push_back(low2[1].second);
  }
  assert(pos.size() <= 14);
  // 排序去重
  sort(all(pos));
  pos.erase(unique(all(pos)),pos.end());

  int cnt = 0;
  // 公式输出
  rep(bits,1,(1<<pos.size())){
    // lcm{set} ^ ( (-1)^|set| (|set| - 2))
    int t = __builtin_popcount(bits);
    int pwr = (t%2?-1:1) * (t-2);
    cnt += abs(pwr);
  }
  printf("%d\n",cnt);

  rep(bits,1,(1<<pos.size())){
    // lcm{set} ^ ( (-1)^|set| (|set| - 2))
    int t = __builtin_popcount(bits);
    int pwr = (t%2?-1:1) * (t-2);
    if(!pwr) continue;
    int op = pwr < 0 ? 1 : 0;
    pwr = abs(pwr);
    while(pwr--){
      printf("%d %d",op,t);
      rep(i,0,pos.size()){
        if(bits & (1<<i)){
          printf(" %d", pos[i]);
        }
      }
      printf("\n");
    }
  }
  return 0;
}

总结

光是这个容斥公式, 我都得不出, 全靠手工算了个特例

知识点1, kmin/kmax 反演 有地一个公式

知识点2, 从gcd 集合, 推理到gcd2集合的元素个数上限和一种构造方案

gcd2(S) => gcd2(T) => kmin容斥

思考角度从小量枚举和得到的线性公式是可以的,而主要缺乏相关反演知识,应该去补充

然后有感觉到可能被值的范围限制了运算, 但是没想到考虑从gcd 演变到gcd2

参考

官方

luogu

反演