Atcoder abc295

發表於 更新於 分類於 ， Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘
E(概率论)Ex(DP)

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

E - Kth Number

给长n数组a, $a[i]\in[0,M]$

对于每个$a[i]=0$,等概率修改$a[i]\in[1,M]$

所有修改完后, sort a

问 exp(A[k]) mod 998244353

N 2000

M 2000

4s

1024mb

我的思路

$ans = \sum_{v=1\to m} v\cdot p(v)$

其中$p(v)$表示 $v$是排序后第$k$小的概率

有$z$个0,其中$z_1$个改为$< v$,$z_2$个改为$=v$,剩下$z-z_1-z_2$个改为$> v$

$p(v) \cdot z^m = \sum_{z_1,z_2} \binom{z}{z_1}\binom{z-z_1}{z_2} (v-1)^{z_1}1^{z_2}(m-v)^{z-z_1-z_2}$, 其中 $z_1 + count(<v) < k$且$z_1+z_2+count(\le v) \ge k$

看上去是$O(m n^2)$的

题解

$ans = \sum_{v=1\to m} v\cdot (第k小的是v)$,

$= \sum_{v=1\to m} (第k小的 \ge v)$

没了

Ex - E or m

二维N行,M列二维数组A, 初始全0

  • 对于每一行，对于一个前缀长度的所有0改为1
  • 对于每一列，对于一个前缀长度的所有0改为1

S={所有能通过上述方法得到的二维数组}

M,N [1,18]

给二维数组X,N行M列,由0/1/?组成

有$2^{?个数}$ 问有多少是在集合S中的

我的思路

一个属于S的二维数组, 满足对于每个1, 它向上或者向左侧有连续的1,

所以一旦一个方向不连续, 则另一个方向一定全是1

F(szN,szM, col)

F(N,M,M) = (双向1)F(N-1,M-1,M-1) + (纵向1)F(N,M-1,M-1) + (横向1)F(N-1,M,M) + F(N,M,M-1)

F(N,M,j) = j 右侧不考虑, 双向单向去

4叉，状态很大

上面其实再简化一点是 F(行, 列集合, 当前处理列)

这样看起来就可以做了？

O(n 2^m m)的复杂度, $18 \cdot 2^{18}\cdot 18=84934656$

代码

https://atcoder.jp/contests/abc295/submissions/41881127

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
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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;}

const int N = 18;
bool solved[N][1<<18][N]; // mint = 0并不表示没计算过
mint ans[N][1<<18][N];

char s[N][N+1];

int m;

mint f(int r,int mask,int c){
  if(mask == 0) return 1; // 所有列都删除了
  if(r == -1) return 1; // 所有行都删除了
  assert(r>=0);
  assert(mask < (1<<m));
  assert(c >= 0);
  mint &res = ans[r][mask][c];
  if(solved[r][mask][c]) return res;
  if(!(mask & (1<<c))) { // 这列已经删掉
    if(c) return res = f(r,mask,c-1);
    else  return res = f(r-1,mask,m-1);
  }
  solved[r][mask][c] = true;
  int r1 = 0; // 同 row 1
  int rq = 0; // 同 row question
  int c1 = 0; // 同 col 1
  int cq = 0; // 同 col question
  rep(j,0,c) { // 左侧点统计时注意已经删除的列 看作是1
    r1 += s[r][j] == '1' or !(mask & (1<<j));
    rq += s[r][j] == '?' and (mask & (1<<j));
  }
  rep(i,0,r) {
    c1 += s[i][c] == '1';
    cq += s[i][c] == '?';
  }
  auto rmNothing=[&]()->mint{ return c?f(r,mask       ,c-1):f(r-1,mask       ,m-1); };
  auto rmCol    =[&]()->mint{ return c?f(r,mask-(1<<c),c-1):f(r-1,mask-(1<<c),m-1); };
  auto rmRowCol =[&]()->mint{ return f(r-1,mask-(1<<c),m-1);};
  auto rmRow    =[&]()->mint{ return f(r-1,mask,m-1); };

  auto fill0=[&](){ res += rmNothing(); }; // 填0
  auto fill1=[&](){ // 填1
    // 行列至少一个满
    if(r1 == c and c1 == r) { // 行列已经全满
     res += rmRowCol();
    }else if(r1 == c) { // 行已经满,列任意
      res += rmRow();
    }else if(c1 == r) { // 列已经满,行任意
      res += rmCol();
    }else if(r1+rq != c and c1+cq == r) { // 行不能满，列可以满
      res += rmCol();
    }else if(r1+rq == c and c1+cq != r) { // 行可以满, 列不能满
      res += rmRow();
    }else if(r1+rq == c and c1+cq == r) { // 都可以满, 但都没满, 容斥
      res += rmRow() + rmCol() - rmRowCol();
    }else{ // 都不能满
      // 失败
    }
  };

  if(s[r][c] == '0'){ // 忽略行列选择
    fill0();
  }else if(s[r][c] == '1'){
    fill1();
  }else{ // == '?'
    fill0();
    fill1();
  }
  return res;
}


int main(){
  int n=read();
  m=read();
  rep(i,0,n) scanf("%s",s[i]);
  printf("%d\n",f(n-1,(1<<m)-1,m-1).val());
  return 0;
}

总结

E

卡住了

又是经典的，但是做的次数不多的 sum i f(x=i) = sum f(x >= i)

Ex

橙题而已, 觉得比E简单，虽然E卡住了是我自己的问题

参考

官方题解