Atcoder abc277

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
G(概率论,DP)Ex(2-SAT)

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

G - Random Walk to Millionaire

n点 m边 无向 简单 连通图

lvl=0 点1出发走k次

每次等概率选u的临点v, 并移动到v

若c[v] == 0: 则 lvl+=1

若c[v] == 1: 则 money += lvl * lvl

求money的期望值

范围

n 3000

m 3000

k 3000

4s

1024mb

我的思路

感觉就 倒着 期望dp?

dp[u][k][l] = 从u出发,走k步, 当前lvl为l 的期望值, ans = dp[1][k][0]

dp[u][k][l] = (sum dp[v][k-1][l+c[v]] + l * l * [c[v]==1] )/child[u]

3维肯定会炸

要是能搞掉 k或者l 就好了

k,l 都有上界, 但k的依赖是依赖k-1, 而l依赖的是更大或者相等

所以说考虑 生成函数 f[u][k] 的$x^l$的系数为 dp[u][k][l]

那么有

$g_u(x) = \frac{ count_{c_v \equiv 1} }{child_u} \sum_{i=0}^\infty x^i$

$x(xg_u(x)’)’ = \frac{ count_{c_v \equiv 1} }{child_u} \sum_{i=0}^\infty i^2 x^i$

$f_{u,k}(x) - x(xg_u(x)’)’ = \frac{ f_{v,k-1}/{x^{c[v] \equiv 1}} }{child_u}$

令 $h_{u,k}(x) = f_{u,k}(x) / x^{c[u]\equiv 1}$

$x^{c[u]\equiv 1} h_{u,k}(x) - x(xg_u(x)’)’ = \frac{ g_{v,k-1} }{child_u}$

并没有什么办法算…

朴素一点

既然 $c_v\equiv 1$时 才产生贡献, 而且这个贡献只与前面的$c=0$个数有关, 那也可以搞成贡献统计?

ans = sum cnt * cnt * p[u][cnt], c[u] == 1

其中 p[u][cnt] 表示不超过 k次移动中, 前面经过$c=0$的次数为$cnt$的概率和

题解

v= 一个具体移动k次的向量, 那么 f(v)表示得到的 money = sum precnt0[0..i]**2 , c[i]==1

xi 表示, 在i前面 的有序对(x,y), c[x]=c[y]=0

(w(长l的一个移动序列),x,y), $x,y \in [1,l], c[x]=c[y]=0$

这样的话, f(v) = (w,x,y) 的个数 其中 w中最后一个点c[l]=1 (也就是上面i和这里l对应, 上面x,y和这里x,y 对应, 再次拆贡献)

$E(f(v)) = \sum p(v) f(v) = \sum_v (\prod_{i=0}^{k-1} \frac{1}{d_{v_i}}) count( (w,x,y) )$, $w$是c=1结尾的v的前缀

对于一个具体的$w$, 前面的$\prod$ 可以看成$w$的那一部分的, 和$w$后续的, 对于给定的$(w,x,y)$,注意$w$的所有后续分支都会有贡献(因此这些贡献的概率和为$1$), 而且都与$x,y$无关(我不太懂题解怎么直接得到的, 智力只能一步一步推过来得到一样的), 所以有

$= \sum_{(w,x,y)} (\prod_{i=0}^{len_w-1} \frac{1}{d_{v_i}})$

也就是一个与 $w$ 相关的概率 与 前面(x,y)的个数, 这样看起来的话, 就和我想的贡献的角度一样了, 只不过这里想着用 (x,y) 来实现平方的描述

转移方程, 考虑 i-1 步 走到u, 然后下一步走到 v, 显然之前所有(w(以u结尾),x,y) 能变成 (w(最后是u,v),x,y), 那么就是 乘上 1/du[u], 而如果c[v]=0, 那么会多出(w(v),v,?),(w(v),?,v), 换句话说就是记录 到$w$的 直接的 概率和p(w) 用于$(v,v)$, 记录到$w$的 统计上$c=0$的概率和, 用于$(v,?\neq v), (?\neq v,v)$, 然后就是 与题意对应的概率和$(x,y)$ 用于$(x\neq v, y\neq v)$, 只有为$c[v]=0$时 发生前两个向第3个转移

dp[i][u][0/1][0/1] = 长度为i, 结束在u 的 所有 (w(以u结尾),x,y)的 概率和(这里不要求结尾的c=1, 只需要统计的时候不统计c=0的即可), 两个 0/1 分别表示x和y 未取 和 取C[w[x,y]] = 0

ans = sum dp[1..k][j=1..n][1][1], c[j]=1

转移:

c[v]=0 时

1
2
3
4
dp[i][v][1][1] = sum dp[i-1][u][0,1][0,1] / du[u]
dp[i][v][1][0] = sum dp[i-1][u][0,1][0] / du[u]
dp[i][v][0][1] = sum dp[i-1][u][0][0,1] / du[u]
dp[i][v][0][0] = sum dp[i-1][u][0][0] / du[u]

c[v]=1 时

1
dp[i][v][a][b] = dp[i-1][u][a][b] / du[u]

注意到 [0][1] 和[1][0] 满足轮换性 永远相等, 还可以降低为0,1,2 3种状态

另一个角度看就是维护2次方程的0次1次和2次系数

代码

https://atcoder.jp/contests/abc277/submissions/36571934

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

vector<int> G[3010];
int c[3010];

mint dp[3010][3010][2][2];// dp[i次移动][停止在j]
                          // [0][0] 用于(v,v), [0][1] 用于(v,\neq v), [1][0] 用于(\neq v,v),[1][1]:(\neq v,\neq v)
mint dinv[3010]; // 1/du[i]
int main(){
  int n=read();
  int m=read();
  int k=read();
  rep(i,1,m+1){
    int u=read();
    int v=read();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  rep(i,1,n+1) c[i] = read();
  rep(i,1,n+1) dinv[i] = mint(G[i].size()).inv();

  dp[0][1][0][0] = 1;
  rep(i,0,k) rep(u,1,n+1) rep(a,0,2) rep(b,0,2) for(auto v: G[u]) rep(na,a,2) rep(nb,b,2){ // na >= a, nb >= b
    if(c[v] == 0 || (na==a && nb==b)) dp[i+1][v][na][nb] += dp[i][u][a][b] * dinv[u];
  }
  mint ans = 0;
  rep(i,1,k+1)rep(j,1,n+1) if(c[j]) ans += dp[i][j][1][1];
  printf("%d\n",ans.val());
  return 0;
}

Ex - Constrained Sums

构建 长n的整数序列序列x, 满足

$x_i \in [0,M]$

$Q$个限制 $x_{A_i} + x_{B_i} \in [L_i,R_i]$

范围

N 10000

M 100

Q 10000

4s

1024mb

题解

之前cf 有这题 见底部连接

区别是 之前M只有10, 这里100

而且之前不是区间, 还有不等关系

总的来说 就是2-sat 要的就是 每个属性正面和反面一定要有且有一个达成

然后 整数离散, 可以拆成 $(\ge x, < x)$ 的点

之前的题里不等关系 是 $a \neq x$ 则有 若 $a \ge x$ 则 $a \ge x+1$, 和若 $a < x+1$ 则$a < x$, 当然这里没有

所以这里所谓区间 可以拆开, 变成

$a_i + a_j \ge x$ 即$a_i < v$ 则 $a_j \ge x -v+1$

$a_i + a_j \le x$ 即$a_i \ge v$ 则 $a_j < x -v + 1$,

就是原题了

代码

https://atcoder.jp/contests/abc277/submissions/36576258

这 人傻常数大, 3833ms

把set和map去了果然快了 1488ms

https://atcoder.jp/contests/abc277/submissions/36576932

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
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;}

class TwoSat{
  vector<int> low; // 能达到的最小的点
  vector<int> dfn; // tarjan 用的深搜访问次序标识
  stack<int> stk; // tarjan 用的stk
  vector<int> res; // tarjan 结果
  vector<vector<int> > p; // 所有点
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = id++;
    stk.push(v);
    for(auto w:p[v]){
      if(dfn[w] == -1){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(res[w] == -1){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
  vector<vector<int> > sccgroup(){
    rep(i,0,2*n) if(res[i]==-1) scc(i);
    vector<pair<int,int> > gi;
    rep(i,0,2*n) gi.push_back({res[i],i});
    sort(gi.begin(),gi.end());
    vector<vector<int> > group;
    rep(i,0,2*n){
      if(i==0||gi[i].first != gi[i-1].first) group.push_back({gi[i].second}); // new group
      else group.back().push_back(gi[i].second); // same group
    }
    return group;
  }
public:
  TwoSat(int SZ):n(SZ){ // 点范围[0..SZ-1]
    low = vector<int>(2*n,-1);
    dfn = vector<int>(2*n,-1);
    stk = {};
    res = vector<int> (2*n,-1);
    p = vector<vector<int> >(2*n);
  }

  bool calc(vector<bool> & ans){
    auto group=sccgroup();
    vector<int> i2g(2*n);
    rep(i,0,group.size()) for(auto idx:group[i]) i2g[idx]=i;
    rep(i,0,n) if(i2g[i*2]==i2g[i*2+1])return false; // 同一个块的真假都在一个scc里
    vector<int> sccmutex(group.size()); // 互斥scc
    rep(i,0,n) { // 每个点的true/false 状态互斥,唯一, 因为建立边时的对称逻辑边
      sccmutex[i2g[i*2]] = i2g[i*2+1];
      sccmutex[i2g[i*2+1]] = i2g[i*2];
    }
    vector<vector<int> > G(group.size()); // 图
    vector<int> degree(group.size(),0);
    // 跨scc的反向边, 做拓扑选择, (因为scc计算后,剩下的一定是偏序不会有环)
    rep(i,0,2*n) for(auto j:p[i]) if(i2g[i]!=i2g[j]) G[i2g[j]].push_back(i2g[i]); // i -> j 反向边
    for(auto &s:G){// 去重
      sort(begin(s),end(s));
      s.resize(unique(begin(s),end(s))-begin(s));
    }
    for(auto &s:G) for(auto t:s) degree[t]++;
    vector<int> d0; // 入度为0
    rep(v,0,degree.size()) if(!degree[v]) d0.push_back(v);
    vector<int> sccpick(group.size(), -1); // scc -1未选, true选/false不选
    rep(i,0,d0.size()) {
      if(sccpick[d0[i]] == -1){ // 没有计算过
        // prinpick("pick %d, unpick %d\n",d0[i],sccmutex[d0[i]]);
        sccpick[d0[i]] = true;
        sccpick[sccmutex[d0[i]]] = false;
      }
      for(auto item:G[d0[i]]) if(!(--degree[item])) d0.push_back(item); // 更新入度排序
    }
    ans = vector<bool>(n);
    rep(i,0,n) ans[i] = sccpick[i2g[i*2+1]];
    return true;
  }
  void then(pair<int,bool> pi, pair<int,bool> pj){ // {i,true/false} -> {j,true/false}
    auto [i,bi] = pi;
    auto [j,bj] = pj;
    assert(i >= 0 && i < n);
    assert(j >= 0 && j < n);
    p[2*i+bi].push_back(2*j+bj);
    if(2*i+bi!=2*j+(!bj)) p[2*j+(!bj)].push_back(2*i+(!bi)); // 自动建立逻辑边
  }
};

// ---------------- lib ----------------

int main(){
  int n = read();
  int m = read(); // xi \in [0,m]
  int q = read();
  TwoSat ts(n*(m+1));
  auto _=[&](int i,int v){return i*(m+1)+v;}; // 编码 a[i] (>=v false, < v true)
  auto ge=[&](int i,int v){return pair<int,bool>{_(i,v),false};}; // greater equal than
  auto lt=[&](int i,int v){return pair<int,bool>{_(i,v),true};}; // less than
  auto chk=[&](int v){return 0<=v && v<=m;};
  rep(i,0,n) rep(v,1,m+1) ts.then(ge(i,v),ge(i,v-1)); // a[i]>=x 则 a[i] >= x-1 小于自动对称逻辑边
  // 不能 < 0, 所以建立 < 0 则 >= 0
  rep(i,0,n) ts.then(lt(i,0),ge(i,0));
  while(q--){
    int i=read()-1;
    int j=read()-1;
    int mn = read();
    int mx = read();
    // a[i]+a[j] >= x = mn, a[i] < v 则 a[j] >= x-v+1
    rep(v,0,m+1) if(chk(mn-v+1)) ts.then(lt(i,v),ge(j,mn-v+1)); // j到i 自动对称
    if(chk(mn-m)){ // mn-v+1 < 0的话 就是全部都可以 不需要建立失败逻辑, 而 a[j] >= x-v+1 > m 才需要
      int v=mn-m;
      ts.then(lt(i,v),ge(i,v));
      ts.then(lt(j,v),ge(j,v));
    }
    // a[i]+a[j] <= x = mx, a[i] >= v 则 aj < x-v+1
    rep(v,1,m+1) if(chk(mx-v+1)) ts.then(ge(i,v),lt(j,mx-v+1)); // j到i 自动对称
    if(chk(mx+1)){ // 同理 建立失败逻辑
      int v=mx+1;
      ts.then(ge(i,v),lt(i,v));
      ts.then(ge(j,v),lt(j,v));
    }
  }

  vector<bool> res= {};
  bool ok = ts.calc(res); // scc 联通分量 标识
  if(!ok){
    printf("-1\n");
    return 0;
  }
  rep(i,0,n) per(v,0,m+1) if(!res[_(i,v)]){ // a[i] >= v
    printf("%d ",v);// ans[i] = v;
    break;
  }
  return 0;
}

总结

G

这里平方转换成点对, 感觉没怎么见过, 有意思, 这样的话可以扩展到x^3 次方就是3个元素的有序对

另一个角度其实 更简单一些, 就是(x^2) 变(x^2+2x+1), 取做0,1,2次的系数维护就完了

算是没啥新知识应该要能自己想出的题, 但没想出

Ex

之前补过

CF 1697F 代码

参考

官方题解

CF 1697F

CF 1697F 我的笔记