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

E - Sugoroku 3

n个格子,初始在1

1到n-1上面都有个骰子, 上面 [0..Ai] 等概率

在到N之前 每次移动 扔出的步数

求期望扔的次数

答案mod 998244353

范围

n 2e5

ai n-i 也就是不会超过n

2s

1024mb

我的思路

记 f(i) = 首次到i的期望次数

i -> j 的期望步数 = 1/(ai+1) + 2/(ai+1)^2 + 3/(ai+1)^3…

s = sum t/(ai+1)^t, t=1…

s/x = sum t/(x)^{t+1}, t=1…

s/x = -(sum 1/(x)^t)’, t=1…

s/x = -((1/x) 1/(1-1/x))’

s/x = -(1/(x-1))’

s/x = 1/(x-1)^2

s = x/(x-1)^2

s = x/(x-1)^2

s = (ai+1)/ai^2

f(i) = sum(f[j=0….i-1]+s[j], 若 j 能到i)

注意到 f[j]+s[j] 的贡献值与i无关, 只有是否贡献有关, 而是否贡献 还是连续的一段

所以用遍历记录贡献和 和失效处来算?

然而并不对, 样例都过不了

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;

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

mint ans[200010];
mint rm[200010];

int main(){
  int n = read();
  mint c=0;
  rep(i,0,n-1){
    int ai=read();
    ans[i] = c;
    c-=rm[i];
    mint s = ans[i] + mint(ai+1)/(mint(ai)*ai);
    rm[i+ai] += s;
    c+=s;
  }
  printf("%d\n",c.val());
  return 0;
}

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

F - Erase and Rotate

给一个长n排列A

问不超过k次操作后能得到的最小字典序列

每次操作 可以删除一个数, 或循环右移1个单位

范围

n 2e5

k [0,n-1]

2s

1024mb

我的思路

考虑两种一个是不移动, 从左删除, 那么就是前 k个中取最小, 然后 后面塞入一个, minPQ维护

右侧移动, 也可以确定 首个数字是啥

问题是 当右侧移动时, 可能和删除是同一个, 这个感觉没啥简单的想法去记录

比如样例数据三

如果看成先移动,再删除, 其实会删除移动过的数字

不知道能不能移动+标记+贪心局部?

然后因为k可能比较大,可以从左侧删除和右侧移动 来得到, 所以考虑两个方向来算, 算完了比较?

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

Ex - I like Query Problem

长n序列A

q个操作

类型1, a[l..r] 整除 x

类型2, a[l..r] = x

类型3, 求 sum a[l..r]

范围

8s

1024mb

n 5e5

q 1e5

ai [1,1e5]

x [2,1e5]

我的思路

感觉就线段树啊

(a/x) = (a/(x * y)) 吧

所以记录一下区间 的操作,

问题是求和的话??

另一个思路就是, 记录连续一样的段, 这样每次操作到连续一样的段上, 如果本来就是一致的就直接除就行了, 而不一致的,每个位置的值在重新赋值前最多除log(2,a[i]) 次

似乎就被均摊了?

然后向上搜集的时候, 注意把原来不一样但除了以后一样的也做合并

似乎就没了?

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

Ex - We Love Forest

一个n点0边的图 G

给序列u[1..m], v[1..m]

做k次操作

每次1~m中等概率选i, 连接ui,vi, (允许重边, 没有自环

对于k = 1…n-1

计算 图是森林的概率

mod 998244353

n 14

m 500

2s

1024mb

我的思路

n 这么小

问题其实就是说k次选择没有出现重边, 也没有产生环的概率

如果只是重边 还很好做, 但是问题是如何判断没有环的概率

然后说 有没有把并查集状态 全部表示出来, 但这样看似乎n又很大

f(x) = x个点的并查集状态的数

考虑和其中最小点1在一起的点数

f(x) = sum binom(x,i) f(x-1-i), i = 0..x-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

n = 15
a = [0 for i in range(n)]
a[0] = 1

fac = [1 for i in range(n)]
for i in range(1,n):
    fac[i] = fac[i-1]*i
def binom(n,m):
    return fac[n]//fac[n-m]//fac[m]

for i in range(1,n):
    for j in range(i):
        a[i] += binom(i-1,j) * a[i-1-j]
    print(i,a[i])

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

1 1
2 2
3 5
4 15
5 52
6 203
7 877
8 4140
9 21147
10 115975
11 678570
12 4213597
13 27644437
14 190899322

状态数量接受不了, 更别提转移代价了

但是如果 容斥看 指定一个mask中的点构成树, 其余任意的话, 能否容斥

并想不出 容斥的单独属性

除非是 每个mask中是森林, 但是既然都是森林了不如直接算出答案

如果每个mask是树, 所有的并交没有意义?

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

G - Pre-Order

给一个n点多叉树的前序遍历结果, 问有多少个树满足, mod 998244353

其中子节点多个时, 按子节点数字从小到大遍历

范围

n 500

2s

1024mb

我的思路

当成父子结构时候, 顺序显然

所以感觉主要在兄弟结构

也就是现在 f(序列a)的方案数

f(a) = a[0]为根, a[1]为第一个树的根, a[i]为第二个树的根

f(a) = g(a[1…])

g(a) = sum f(a[0…i-1]) * g(a[i..])

其中a[0] < a[i]

整合一下 g(a) = sum g(a[1…i-1]) * g(a[i..]), a[0] < a[i]

似乎就没了