Atcoder abc238

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
F(DP)G(莫队)Ex(概率论,DP)

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

F - Two Exams

n个人,每个人两个考试排名分别为pi,qi. 每个人的pi都不同,每个人的qi都不同

问选k个人,且如果i被选,则严格比它排名更小的必选,

方案数 mod 998244353

范围

n 300

2s

1024mb

我的思路

就是拓扑图,然后每次取一个min值, 取了k次,被取出的点集的情况数

想说 属性i = {i以及比它小的全被选}

做容斥, f(点集) = 满足 更小必选要求且 个数为k时,贡献 =1

看似 属性的交满足要求, 但是未被选的任意选择话就难以统计了

题解

把p从小到大排序, q对应位置排序

如果 当前前面有拓扑比它小的没被选,则当前必定不被选

dp[i][j][k] = 排序后的前i个, 已经选择的人数, 最小的未被选的Q值的方案数(因为按照p排序了, 所以之前的p都小于当前的p,所以只关心最小未选的q即可 )

转移

当前选择 dp[i][j][k] = dp[i-1][j-1][k], 满足k > q[i]

当前不选 dp[i][j][k] = dp[i-1][j][min(k,q[i])]

代码

https://atcoder.jp/contests/abc238/submissions/34878579

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
#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;}

pair<int,int> pq[310];
int main(){
  int n = read();
  int k = read();
  rep(i,0,n) pq[i].first = read();
  rep(i,0,n) pq[i].second = read()-1; // [0..n-1]
  sort(pq,pq+n); // p = 1..n, 
  auto dp = vector(k+1,vector<mint>(n+1,0)); // 滚动掉一个维度, dp[前i][选的个数c][min q] = 方案数
  dp[0][n]=1; // inf = n
  rep(i,0,n){
    auto ndp = vector(k+1,vector<mint>(n+1,0));
    rep(c,0,k+1) rep(y,0,n+1){
      if(c<k && pq[i].second < y) ndp[c+1][y]+=dp[c][y]; // 当前选择, 则一定比之前最小未选的q要小
      ndp[c][min(y,pq[i].second)]+=dp[c][y]; // 当前不选, 则随意, 但是要更新min q
    }
    dp = ndp;
  }
  mint res=0;
  for(mint v: dp[k]) res+=v;
  printf("%d\n",res.val());
  return 0;
}

G - Cubic ?

长度为n数组a, q次询问

每次问区间A[l..r]的乘积是否为立方数

范围

n,q 2e5

ai [1,1e6]

3s

1024mb

我的思路

每个数只有Ai, 可以拆成质因子, 然后可以做跳点的感觉

然后因为对A没有修改, 可能也可以离线优化

题解

官方给的随机数打表 + 3bit xor …..

考虑莫队,就是离线 + 分成根号n的区间块

对于质因子小于1e3的, 暴力,

对于大于1e3的每个数至多一个, 利用莫队: 离线 + 分块奇偶排序来做

代码

1052 ms

https://atcoder.jp/contests/abc238/submissions/34879517

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

const int N = 2e5;
const int V = 1e6;
int b[N+10]; // 大于1000 的质因子
int sum[N+10][333]; // sum[i][第j个质数(<1000)] 6n,6n+2,6n+3,6n+4 一定非质数, 所以估计为 < 1000 * 1/3个
int N1000 = 0; // < 1000的质因子个数
int p2i[V+10]; // prime 2 index
int mnp[V+10]; // = 一个质因子
struct qry { int l, r, id; } q[N+10];
int p2c[V+10]; // p2c[质因子(>1000)] = 个数

void modify(int pos,int &c, int d) {
  int p = b[pos];
  if (!p) return ;
  c -= bool(p2c[p]);
  (p2c[p] += d) %= 3;
  c += bool(p2c[p]);
}

int main() {
  int n = read();
  int Q = read();
  int pi = 0; // prime 2 index
  rep(i,2,V+1) if(!mnp[i]){
    mnp[i] = i;
    p2i[i] = pi++;
    if(i < 1000) N1000 = p2i[i] + 1;
    for(int j=2*i;j<=V;j+=i)if(!mnp[j])mnp[j]=i;
  }
  rep(i,1,n+1){ // 1-index 方便前缀 和 区间处理
    int v = read(); // 1e6
    while (v!=1) {
      int p = mnp[v];
      int pwr = 0;
      while (v % p == 0) {
        v /= p;
        pwr++;
      }
      if (p <= 1000) sum[i][p2i[p]] = pwr % 3;
      else b[i] = p;
    }
  }
  rep(j,0,N1000) rep(i,1,n+1) (sum[i][j] += sum[i-1][j]) %= 3; // <1000的质数因子做%3前缀和
  int blk_sz = (int)sqrt(n); // 莫队分块, 块大小
  vector<bool> res(Q,true);
  rep(i,0,Q) q[i] = {read(), read(), i}; // 离线
  rep(i,0,Q) rep(j,0,N1000) if((sum[q[i].r][j] - sum[q[i].l - 1][j]) % 3) res[i] = false; // 小于1000的暴力
  sort(q, q+Q,[=](const qry&q0,const qry&q1){
      int b0 = q0.l / blk_sz; // 左端点对应的块
      int b1 = q1.l / blk_sz;
      return (b0 != b1) ? // 先左端点按块排序
      (b0 < b1):
      ((b0 & 1) ? (q0.r < q1.r) : (q0.r > q1.r)); // 莫队 奇偶优化
  });
  int l = 1; // [l..r], 初始为空
  int r = 0;
  int c = 0; // mod 3 不为 0 的 质因子种数
  rep(i,0,Q){
    while (r < q[i].r) modify(++r,c,1);
    while (l > q[i].l) modify(--l,c,1);
    while (l < q[i].l) modify(l++,c,-1);
    while (r > q[i].r) modify(r--,c,-1);
    if(c) res[q[i].id] = false;
  }
  rep(i,0,Q) printf("%s\n", res[i] ? "Yes" : "No");
  return 0;
}

Ex - Removing People

N 个人顺时针站成一圈, 给定每个人朝向 顺时针/逆时针

做N-1次操作, 每次等概率选一个人, 选最近这个人朝向的人, 代价 = 两人的距离 = 圆上沿着面向的方向的坐标之差 不一定是最短距离

求总代价的期望, mod 998244353

范围

n 300

3s

1024mb

我的思路

首先注意是选人等概率,而不是删人等概率, 对于环来讲一般拆成链加两头的状态

既然最后会留下一个人, 可以考虑钦定一个人来算, 来拆, 中间这个人始终不会被删除

问题变成了

PLLRRRLRLRLRP

两头P不应该被删,最后只剩下P的链上问题

n有300, bitdp肯定不行

感觉搞顺序很难搞, 不如考虑每个代价对总代价的贡献概率

1
2
P...L....?...P
    i    j

i -> j 的贡献概率是i上是L, 某次选中i时 i..j 之间的被删完了, 当前剩余t个,

f(s,i,j,t) = s开始剩余t个且 i->j 之间被移除了,i,j还在的概率, 然而似乎这状态就N^4 了, 还根本没法转移和计算

题解

若p为删除的人的下标数组, p[n] 也就是最后剩下的人

再考虑反过来,不是删除,而是从空的开始放置

每次被放置的人, 需要明确看到他的人 是顺时针还是逆时针

然后就是 方案数 / n! mod 998244353

num[l][r] = 当l,r已经放好后, [l+1..r-1]的放的方案数

cost[l][r] = 当l,r已经放好后, [l+1..r-1]的放的代价和

考虑[l+1..r-1]中先放哪一个

num[l][r] = sum (num[l][i] * num[i][r] * ((a[l] == 'R') + (a[r] == 'L')) * binom(r-l-2,i-l-1))

因为当选了i以后,[l][i] 和[i][r] 内部的操作顺序可以任意穿插 所以还有个binom

而 从删除的角度想, 选左边 ==’R’时, 和右边==’L’时, 虽然都是删除i 但是对应是两个方案, 所以中间是

cost[l][r] = sum ( (num[l][i]*num[i][r]*((a[l]=='R')*(i-l)+(a[r]=='L')*(r-i))+num[l][i]*cost[i][r]*(a[l]=='R'+a[r]=='L') + cost[l][i]*num[i][r]*(a[l]=='R'+a[r]=='L') ) * binom(r-l-2,i-l-1))

分别是 这次操作的代价, 和 子操作代价 * 次数

O(n^3)

代码

https://atcoder.jp/contests/abc238/submissions/34895842

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
#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++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}

const int N = 300;
mint fac[N+10] = {1};
mint ifac[N+10];
mint binom(int n,int m){ return (m<0 || n<m)?0: fac[n]*ifac[m]*ifac[n-m];}

char s[N+10];
mint num[N+10][N+10];
mint cost[N+10][N+10];

int main(){
  rep(i,1,N+1) fac[i] = fac[i-1] * i;
  ifac[N] = fac[N].inv();
  per(i,0,N) ifac[i] = ifac[i+1] * (i+1);

  int n = read();
  scanf("%s",s);
  rep(i,0,n) num[i][(i+1)%n] = 1;
  rep(d,1,n+1) rep(l,0,n){ // 距离d从小到大
    int r = (l+d)%n;
    rep(p,1,d){ // [l...l+p...l+d]
      int i = (l+p)%n;
      int c1 = int(s[l]=='R')   + int(s[r]=='L');
      int c2 = int(s[l]=='R')*p + int(s[r]=='L')*(d-p);
      num[l][r]  +=  num[l][i]*num[i][r]*c1                                                 *binom(d-2,p-1);
      cost[l][r] += (num[l][i]*num[i][r]*c2+num[l][i]*cost[i][r]*c1+cost[l][i]*num[i][r]*c1)*binom(d-2,p-1);
    }
  }

  mint ans = 0;
  rep(i,0,n) ans += cost[i][i];
  ans *= ifac[n];
  printf("%d\n",ans.val());
  return 0;
}

总结

F

排序一个, dp另一个

G

hash + 随机 学也学不会, 放弃, (虽然我知道n-bit xor 意义

莫队, 上次学已经是两年前了, 这么久没有用过, 再遇到还是觉得神奇 又 有效

Ex

逆向处理

对于这种中间顺序可以变动的, 还互相关联的, 完全不会

概率与次数转换

感觉还是找局部性吧, 这样反过来以后, num和cost只关心之间的,而对于外部的贡献,变成从外部的binom

参考

官方题解

https://yexiaorain.github.io/Blog/algo/mo/