Atcoder abc270

發表於 更新於 分類於 ， Disqus： 文章字數： 2.5k 所需閱讀時間 ≈ 8 分鐘
F(最小生成树)G(数论,BSGS)Ex(概率论,DP)

https://atcoder.jp/contests/abc270/tasks

F - Transportation

n 个点

Xi 价格 点i 修 airport

Yi 价格 点i 修 harbor

Zi 修路 ui<->vi, m条

最小代价 所有点连通

范围

n 2e5

m 2e5

xi,yi,zi[1,1e9]

4s

1024mb

我的思路

如果没有airport/harbor, 那么就是 最小生成树

如果有

则会有两个点同时有 两种交通工具, 或者一个点同时三个交通工具

如果能确定基础代价, 那么增加连通代价 要么是路, 要么是某个交通工具

n这么大 也不能bitmask

如果只有一种

那么就是 先考虑所有都建立, 然后每次可以拆一个 贡献 -Xu + min(road[u,v?])

不会了

题解

虚拟节点, 让 i 和 飞机节点连, 让i和船节点连

然后考虑 有无飞机节点, 有无船结点 的最小生成树, 4 * O(最小生成树没了)

代码

https://atcoder.jp/contests/abc270/submissions/35813110

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
#include <bits/stdc++.h>
#include <atcoder/dsu>
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;}
#define INF 0x3f3f3f3f3f3f3f3f

int n;
ll solve(vector<tuple<ll,int,int> >&e){
  ll ret=0;
  sort(e.begin(),e.end()); // 最小生成树
  atcoder::dsu d(n+2);
  for(auto [l,u,v]:e)if(!d.same(u,v)){
    d.merge(u,v);
    ret+=l;
  }
  return d.size(1)<n?INF:ret;
}

int main() {
  n=read();
  int m=read();

  vector<tuple<ll,int,int> > G;
  vector<ll> x(n),y(n);
  rep(i,0,n)x[i]=read();
  rep(i,0,n)y[i]=read();
  rep(i,0,m){
    int u=read()-1; // 0-index
    int v=read()-1;
    ll d=read();
    G.push_back({d,u,v});
  }

  ll ans=INF;
  const int airport=n;
  const int harbor=n+1;
  rep(k,0,4){
    auto e=G;
    if(k&1)rep(i,0,n)e.push_back({x[i],i,airport});
    if(k&2)rep(i,0,n)e.push_back({y[i],i,harbor});
    ans=min(ans,solve(e));
  }
  printf("%lld\n",ans);
  return 0;
}

G - Sequence in mod P

令 x=s (第0次)

每次 x= (ax+b) % p

问第几次 x==g 或不存在这种情况

范围

100组测试

p 1e9, 是质数

$a,b,x,g \in [0,p)$

4s

1024mb

我的思路

显然 x的序列成环,

对环的话 快慢指针, 但这里 t = 100, p 1e9, 显然希望能做到 sqrt(p)的级别, 如果仅仅快慢指针 也是O(p) 的不行

题解

是Baby-step Giant step

可以找最小n , f^n(x) = y

对于任意M, 找最小 j \in [0,M), f^{iM}(x) = (f^-1)^j(y), ???

如果A==0 那么很好算

考虑A!=0, 如果有X_n=T, 那么n<=P

令$M= \lfloor \sqrt{p} \rfloor$

令其逆方程为$f^{-1}(x) = Cx+D$, 显然 $0 < A < P$ 一定存在

考虑 $f^i(x) = f(f^{i-1}(x))$

那么和baby-step giant step 类似的

$f^{Mi-j}(x) = g \pmod{p}, j \in [0, M) $

$(f^{M})^i(x) = g \cdot (f^{-1}(x))^j \pmod{p}$

那么 i和j的取值范围都是 $O(\sqrt{p})$

Baby Step,Giant Step 高次同余方程

$a^x \equiv b \pmod{p}$

已知a,b,p, 且p为质数, gcd(a,p) = 1

求x

令 $x=it-j, t = \lfloor \sqrt{p} \rfloor, 0\le j < t$, 这里也可以是+j, 就是上面题解用的, 本质是类似的, 复杂度也都是一样的, 实际上 这里+会更好, 因为要求最小时, 可以最小i * m + 最小j

注意到 $i$ 和 $j$ 为非负整数时, 可以让x取完所有非负整数

$a^{i \lfloor \sqrt{p} \rfloor - j} \equiv b \pmod{p}$

即 $(a^{\lfloor \sqrt{p} \rfloor})^i \equiv b\cdot a^j \pmod{p}$

注意到 如果 存在$x$使表达式成立, 则最小的 $x < p$

因此 $i \cdot t - t < i \cdot t - j < p$

$i < p / t + 1$

有 i和 j的范围都是 $O(\sqrt{p})$ !!!

搞个hash 就好了

代码

https://atcoder.jp/contests/abc270/submissions/35937294

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

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

int solve(int p,int a,int b,modint l,modint r){ // x0=s, x=ax+b mod p, x ?= g
  if(l==r)return 0;
  if(a==0){ // l b b b b b
    if(b==r)return 1;
    return -1;
  }

  // f(x) = ax+b : f^-1(x) = (x-b)/a = 1/a x + (-b)/a = cx+d
  modint c=modint(1)/a;
  modint d=modint(-b)/a;
  auto invf=[=](modint x){return x*c+d;};
  int m = sqrt(p); //  (f^m(x))^i == b (f^-1(x))^j (mod p) => f^{mi+j}(x) = b

  // 枚举等式右侧
  unordered_map<int,int>right;
  rep(j,0,m){ // 枚举右侧
    if(!right.count(r.val())) right[r.val()]=j; // 避免重复, 最小j
    r=invf(r);
  }

  // 计算 f^m(x) = A'x+B'
  modint A=1;
  modint B=0;
  rep(j,0,m){ // f(A'x+B') = a(A'x+B')+b = aA'x + (aB'+b)
    A*=a;
    B=B*a+b;
  }
  auto fm=[=](modint x){return A*x+B;};
  rep(i,0,p/m+2){
    if(right.count(l.val())) return i*m+right[l.val()]; // i 越大 i*m+j 越大
    l=fm(l);
  }
  return -1;
}


int main(){
  int t=read();
  while(t--){
    int p = read();
    int a = read();
    int b = read();
    int s = read();
    int g = read();
    modint::set_mod(p);
    printf("%d\n",solve(p,a,b,s,g));
  }
}

Ex - add 1

给定 n个元素非负数组A, A[1]=0, A[N] >0

有n个计数器V, 所有初始Vi=0

重复 直到 所有 计数器, Vi >= Ai

每次 等概率选择一个 设它为0, 其它全部+1

输出期望次数 mod 998244353

范围

3s

1024mb

n 2e5

ai [0,1e18], 单调递增的提供

我的思路

概率论

考虑什么时候结束, 那么最后一次一定是选择了一个Ai = 0 的, 且剩余的都 >= Ai-1, 且存在至少一个原来 = Ai-1

对于一些操作结束状态

S集合: Si 表示 第i个的值 到操作结束时 >= Ai 的连续满足的最早时刻,

max(S) 表示 所有 位置都满足大于, 也就是 所有位置满足的最早时刻

E(max(S)) = 要求的期望次数

E(min(T)) = 其中一个位置满足后, 不再被破坏 >= Ai 的最早时刻

对于 min(T) = t

那么 就是 集合T中 某一个i, t-1次都没满足 >= Ai(?????), t次时满足了(选的不是i), 之后一直没有选i

感觉不同的i还要相互容斥??

而且和之前补的 abc242 Ex 不同的是, 这里还有清零操作

题解

另C 为计数数组

state = max(Ai-Ci) 也就是最大的距离差值!!!!

初始显然 state = An

结束状态就是 state = 0

那么 考虑一次选择的转移是

max( Ai, max(Aj-(Cj+1))), i\neq j

也就是 把Ai变成0, 其它Cj+=1

如果原来的 Ai-Ci == state, 那么 Ai>=state >= state-1, 所以 max( Ai, max(Aj-(Cj+1)) <= state - 1 < Ai) = Ai

如果原来的 Ai-Ci < state, 那么 max(Ai,max(Aj-(Cj+1))) = max(Ai,state - 1)

换个角度

… <= a[r] < state <= a[r+1] <= …

那么显然k 是由 右侧 产生的,

那么如果选了左侧的, 则 state -= 1

如果选了右侧的, 则 变成 Ai

因此有转换关系

e[k] = 从state=k到结束的剩余期望次数

$e_k = \frac {r\cdot e_{k-1} + \sum_{i=r+1}^n e_{A_i} }{n} + 1$ , 根据上面的 变化关系, 要么是 r种 让state-1的要么是 变成比它大的

交换等式

$e_{k-1} = \frac{1}{r} (n(e_k-1) - \sum_{i=r+1}^n e_{A_i})$, 这样就是 依赖的都比它自身下标大了, 但实际上结束状态是 e[0] = 0

这个 倒着的并不好算

不过发现从计算顺序来讲, 每一项都依赖 于 最后一项e[a[n]]

一般来讲, 两个办法, 除掉或减掉, 但 这里 x[0]=0 除掉 难以恢复, 考虑减掉, 注意到右侧 内部的系数也是r, 所以左右系数都是1,

令 $y_i = e_i - e_{A_N}$ (官方题解这里是反过来减的 会影响一点系数(比如$y_k-1$), 不过总体方向一样

$y_{k-1} = e_{k-1}-e_{A_N}=\frac{1}{r} \left(N(e_k-1)-\sum_{i=r+1}^N e_{A_i} \right) - e_{A_N} = \frac{1}{r}\left(N(y_k-1)-\sum_{i=r+1}^N y_{A_i} \right)$

这样 就可以递推了, 然后通过 $e_0 = y_0+e_{A_N}$ 算出$e_{A_N}$ 后, 再通过$e_i = y_i + e_{A_N}$ 算出$e_i$

显然 对于 $A_N \le 10^{18}$ 会TLE

注意到N 没那么大

考虑计算$y_{A_i}$

令$s_r = \sum_{i=r+1}^N y_{A_i}$ 表示后缀和

$y_{k-1} = \frac{1}{r}\left(N(y_k-1)-s_r \right)$

然后就是初中 的等比思想, $f(x) = ax+b$ 要计算$f^m(x)$

那么就是 变成 $f(x) + t = a(x+t)$ 的形式, 然后有 $f^m(x) + t = a^m (x+t)$

t 容易计算 $t = \frac{b}{a-1}$

回到题目

$y_{k-1} + \frac{\frac{-N-s_r}{r}}{\frac{N}{r}-1} = \frac{N}{r}\left(y_k + \frac{\frac{-N-s_r}{r}}{\frac{N}{r}-1}\right)$

那么有

$y_{A_r} = (\frac{N}{r})^{A_{r+1}-A_{r}} (y_{A_{r+1}} - \frac{N+s_r}{N-r}) + \frac{N+s_r}{N-r}$

至此可算

注意到 r和N-r 都是小于 998244353 的非0值, 所以没有除0问题

又注意到 这里 A[i] == A[i+1] 时

$y_{A_r} = (\frac{N}{r})^{A_{r+1}-A_{r}} (y_{A_{r+1}} - \frac{N+s_r}{N-r}) + \frac{N+s_r}{N-r} = 1 \cdot (y_{A_{r+1}}- t ) + t = y_{A_{r+1}}$ 也满足递推式 ,所以 可以不用找不同值直接 倒着for

代码

https://atcoder.jp/contests/abc270/submissions/35940720

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
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;)

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

int main(void) {
  int n=read();
  vector<ll>a(n);
  vector<mint> y(n); // y[n-1]=0; y[i] = e[a[i]] - e[a[n-1]];
  mint s=0; // y的后缀和
  rep(i,0,n) a[i] = read();
  per(i,0,n-1){
    mint t=(n+s)/(n-(i+1));
    y[i]=((mint)n/(i+1)).pow(a[i+1]-a[i])*(y[i+1]-t)+t;
    s += y[i];
  }
  printf("%d\n",(-y[0]).val());
  return 0;
}

总结

F

又卡蓝题了

虚拟节点表示并查集关系 转化点代价到边上

G

数论又不会, 既然p是质数那么显然有逆函数, 很有道理 , 这点都没想到,太蠢了我

高次同余baby-step giant-step, 没学过, 神奇

Ex

这转化 和 分析 完全没想到, 总觉得 最大和所有关联, 但是 实际上可以转化成 大于的部分和小于的部分

剩下就是DP和DP优化了

参考

官方题解