Atcoder abc249

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
G(线性基)Ex(概率论,线性代数,排列组合)

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

G - Xor Cards

n个卡, 每张有正面ai,背面bi

求让正面的 xor 和 <= K时, 背面 xor和 最大

求最大值

范围

n 1000

k (1<<30)

ai,bi [0,1<<30)

我的思路

对于xor和不等式没啥想法

一个是 对结果从高位到低位去贪心

比如 第i位 结果xor为1

那么 假设当前集合中, 对应b的i位为1的选奇数个, i位为0的选偶数个

但如何控制与Ai 的关系

第二个方向就是 xor 是不是有线性基, 但是如何把线性基的 结果大小 和 对应的xor和 尽量大

第三个就是N只有1000, 有啥n^2 的方法

dp[i][j], 前i的j个, 感觉”个数” 和目标之间没啥关系

题解

有2^N-1 中选择方式, 然而只有2^30种可能的值

而对于正反面 2^{30} 2^{30} = 2^{60} !!!!!

啊 好有道理, 因为如果你把 正反面 通过位移 和 或 就可以变成一个 2^{60} 的数!!!!!

而这个数的异或运算再拆分 和分别异或是一样的

所以 考虑不超过60张卡的表示

显然 如果把 卡(aj,bj) 换成(ai^aj,bi^bj). 不会影响答案(易证,线性基知识)

然后对线性基做行变换, 显然 主元为1的不超过 60行

变化完后, 就是对60行进行考虑

并不能从高到低做数位dp,因为是xor不是+,没有局部更大的性质

考虑从高位bit对应的行向量开始, 记 A’,B’ 为已经选了的xor和

对于ai设最高位1是第k位, 那么后续的任意选择 只会影响比k位更低的位,

也就是,如果比k位更低的从现在开始随便选, 那么就是剩下的 考虑任意选和当前的B’ xor 尽量大

而不是随便选时 其实也说明了高位相等,只有相等的长度维度, 可以继续向后考虑

然后 当随便选时,

其实,也是B’必选, 后面B 类似前面用 xor 替换掉高位的方法 即可, 然后直接贪心从高到低

代码

https://atcoder.jp/contests/abc249/submissions/35178644

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
#include <bits/stdc++.h>
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 sweep(vector<ll>& c, int W) {
  int n = c.size();
  int rank = 0; // 矩阵的秩 主元行数
  per(d,0,W){
    int k = rank; // 处理 [rank...n-1] 行
    ll bit = (ll)1<<d;
    while (k < n and !(c[k] & bit)) k++; // 找d位为1的
    if(k >= n) continue; // 未找到
    swap(c[k], c[rank]); // 交换行
    rep(i,0,n)if(i!=rank && (c[i]&bit)) c[i] ^= c[rank]; // ai^aj 主元列其它为0
    rank ++;
  }
  return rank;
}

ll maximize(vector<ll> c, ll x, int W) {
  int n = sweep(c, W);
  rep(i,0,n) x = max(x, x ^ c[i]);
  return x;
}

int main(){
  const int W = 30;
  int n = read(); // 
  int k = read();
  vector<ll> c(n);
  rep(i,0,n){
    ll a = read();
    ll b = read();
    c[i] = (a << W) | b;
  }

  n = sweep(c,2*W);
  if(n == 0){ // 全是0向量
    printf("0\n");
    return 0; 
  }
  vector<int> a(n), b(n);
  rep(i,0,n){
    a[i] = c[i] >> W;
    b[i] = c[i] & ((1 << W) - 1);
  }
  if (a[n-1] > k) {
    printf("-1\n");
    return 0; 
  }
  int m = 0; // count(a[] > 0)
  while (m < n and a[m] > 0) m++;

  ll ans = 0;
  ll p_a = 0;
  ll p_b = 0;
  rep(i,0,m){
    int msb = 1; // 获得a[i]的最高bit
    while ((msb*2) <= a[i]) msb*=2;
    if((p_a | (msb*2-1)) <= k) { // 若当前及后面任意
      ans = max(ans, maximize(vector<ll>(b.begin()+i  , b.end()), p_b,W));
      break;
    }
    if ((p_a | (msb - 1)) <= k) { // 当前不选 后面任意
      ans = max(ans, maximize(vector<ll>(b.begin()+i+1, b.end()), p_b,W));
      // 当前选
      p_a ^= a[i];
      p_b ^= b[i];
    } // 当前不选后面都不能任意的话, 那么必定不选
  }
  if (p_a <= k) ans = max(ans, maximize(vector<ll>(b.begin() + m, b.end()), p_b, W)); // 全部考虑后, 剩余的
  printf("%lld\n",ans);
  return 0;
}

Ex - Dye Color

1..n 个球, 颜色Ai

重复直到所有颜色一样

有2^n 个下标子集(包括空集)

等概率选一个下标子集, 设子集元素个数为k, 再等概率的从1..n中选一个k个数的排列, 让 color[子集下标[i]] = p[i]

求期望操作次数

范围

n 2000

ai [1,n]

3.5s

1024mb

我的思路

看起来花里胡哨, 但感觉说, 要么直接颜色就相等了, 要么每次选的下标 重新染色,就会让其中一个1,剩余的全部非1

所以 最终一定全部变成1

所以变成 1 的个数变化转化概率?

假设当前k个1, 那么(2^{n-k} -1)种选择 多1个1

k 2^{n-k} 种选择,1不变

c(k,i) 2^{n-k} 种选择, 1减少(i-1)个, 即变成(k-i+1) 个1

所以可以直接得到1之间2000x2000的转移概率矩阵

E(X) = sum x * 初始 * 矩阵^x * 收集

ans = A (B(E-B)^-1(E-B)^-1) C

A = [0,0,0,0,0,…,0,[1个数]=1,0…,0,0,0]

C = [0,0,0,0,0,0,…,0,1]^T

所以 矩阵这样等比数列能这样算? 以及这就线性代数+概率论+排列组合就没了?

似乎读错题了, 是从1…N 中等概率选 k个不同数的排列,不是1..k

题解

f(A) = A的操作期望次数

f(全部相等) = 0

f(A) = 1 + sum(p(A->A’) f(A’))

定义B_{A,j} = (Ai=j)的个数

如果有办法找到函数g和常数C让 f(A) = sum g(B_{A,i}) - C 横成立, 那么可以解决, (也就是A的期望 与各个值的出现次数 单独有关系

$ \sum_{i=1}^{N} g(B_{A,i}) = f(A) + C$

$= 1 + \sum E_{A,A’} f(A’) + C$

$= 1+ \sum E_{A,A’} (\sum_{i=1}^{N} g(B_{A’,i})-C) + C $

$= 1+ \sum E_{A,A’} \sum_{i=1}^{N} g(B_{A’,i})$

再来, 再假设 如果 $g(B_{A,i}) = \frac{1}{N} + \sum E_{A,A’} g(B_{A’,i})$, 上式依然成立

注意到, B的定义虽然看起来与A和i有关, 但实际上值域是[1,N]的整数, (当给定N时)

$g(i) = \frac{1}{N} + \sum_j=0^N p_{i,j} g(j)$, 其中P从上面E转变来

而是我们会得到 大于等于n个g(i)的线性方程, 而根据线性代数的知识, 它们的rank <= n

而根据上面的知识 每次最多让一个数增1

所以 j <= i+1

$\begin{pmatrix}
P_{0,0}-1 & P_{0,1} & 0 & 0 & \dots & 0 & 0\\
P_{1,0} & P_{1,1}-1 & P_{1,2} & 0 & \dots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
P_{N-1,0} & P_{N-1,1} & P_{N-1,2} & P_{N-1,3} & \dots & P_{N-1,N-1}-1 & P_{N-1,N} \\
\end{pmatrix}\begin{pmatrix}
g(0) \\
g(1) \\
\vdots \\
g(N) \\
\end{pmatrix}=\begin{pmatrix}
-\frac{1}{N} \\
-\frac{1}{N} \\
\vdots \\
-\frac{1}{N} \\
\end{pmatrix}$

令 g(0) = 0 , 可以n^2,

同时,需要证明P_{i,i+1} != 0 mod 998244353

也就是这个Pi,j 还是得算

看它的意义, 注意到 虽然这个来自于 B_{A,i} , 但是 会发现在B_{A,i} 中, 这个值的变化概率, 和变化后的个数, 与其它无关(! 是因为这个无关性 所以才想到 前面的g拆分吗?), 所以这个概率也就是 一次操作后i个变成j个概率

有i个颜色X

设第一步 选的球中有S个颜色是X

那么 重新染色后 有一个球被染色成X的概率是

$\displaystyle \frac{\displaystyle \sum_{k=0}^{N-i} \binom{N-i}{k} \times \binom{i}{S} \times \frac{k+S}{N}}{2^N}$

$ = \displaystyle \frac{\binom{i}{S}}{2^N} \times (\displaystyle \sum_{k=0}^{N-i} \binom{N-i}{k} \times \frac{k}{N} + \displaystyle \sum_{k=0}^{N-i} \binom{N-i}{k} \times \frac{S}{N})$

$ = \displaystyle \frac{\binom{i}{S}}{2^N} \times (\frac{N-i}{N}\displaystyle \sum_{k=0}^{N-i-1} \binom{N-i-1}{k} + \displaystyle \frac{S}{N}\sum_{k=0}^{N-i} \binom{N-i}{k} )$

$ = \displaystyle \frac{\binom{i}{S}}{2^N} \times (\frac{N-i}{N} 2^{N-i-1} + \frac{S}{N}\ 2^{N-i} )$

$ = \displaystyle \binom{i}{S} \times \frac{N-i+2S}{N2^{i+1}}$

k表示不是颜色X被选择的个数, 第一部分就是其它颜色的选择情况

第二部分 i个颜色X的中选S的方案,

第三部分, 就是N个中选k+S 出现X的概率,

分母就是所有方案

那么这个会对$P_{i,i-S+1}$产生贡献

类似的, 选了S个, 但是染色没有X

$\displaystyle \frac{\displaystyle \sum_{k=0}^{N-i} \binom{N-i}{k} \times \binom{i}{S} \times (1-\frac{k+S}{N})}{2^N}$

$ = \displaystyle \binom{i}{S} \times \frac{N+i-2S}{N2^{i+1}}$

那么这个会对$P_{i,i-S}$产生贡献

因此P_{i,j} 可以算出

$P_{i,j} = \displaystyle \binom{i}{i-j+1} \times \frac{N+i-2j+2}{N2^{i+1}} + \displaystyle \binom{i}{i-j} \times \frac{N-i+2j}{N2^{i+1}}$

然后要证明 P_{i,i+1} mod 998244353 都不为0, 中间其它的可以为0, 因为不做高斯消元, 直接在矩阵上硬算

P_{i,i+1} 对应的是S=0

$\displaystyle \frac{\displaystyle \sum_{k=0}^{N-i} \binom{N-i}{k} \times \frac{k}{N}}{2^N} = \displaystyle \frac{N-i}{N2^N} \displaystyle \sum_{k=0}^{N-i-1} \binom{N-i-1}{k} = \displaystyle \frac{N-i}{N2^N} 2^{N-i-1} = \frac{N-i}{N2^{i+1}}$

然后算出g以后 C也很容易得到

因为 f(A全部相等) = 0 = sum g() + C = g(0)+g(0) +…+g(0) + g(n) - C

C = g(n)

注意到增广矩阵 可以同时乘上 数 ,这里 把两边都乘上 $N2^N$

$P’_{i,j} = \displaystyle \binom{i}{j-1} \times (N+i-2j+2) \times 2^{N-i-1} + \displaystyle \binom{i}{j} \times (N-i+2j) \times 2^{N-i-1}$

$P’_{i,i+1} = (N-i)2^{N-i-1}$

右侧增广列变成$-2^{N}$

代码

https://atcoder.jp/contests/abc249/submissions/35188361

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

#define N 2000
int cnt[N+10];// input value 2 count
mint p2[N+10]={1}; // pow2
mint g[N+10];// g[0] = 0
mint binom[N+10][N+10];

int main(){
  int n=read();
  rep(i,1,n+1)cnt[read()]++;

  binom[0][0]=1;
  rep(i,1,n+1){
    p2[i]=p2[i-1]*2;
    binom[i][0]=1;
    rep(j,1,i+1)binom[i][j]=binom[i-1][j]+binom[i-1][j-1];
  }

  rep(i,0,n){
    mint &r=g[i+1]=(g[i]*n-1)*p2[n];
    rep(j,0,i+1)r-=((j>0?binom[i][j-1]*(n+i-2*j+2):0)+binom[i][j]*(n-i+2*j))*p2[n-i-1]*g[j];
    r/=p2[n-i-1]*(n-i);
  }

  mint ans=-g[n];//-C:g(0)+g(0)+...+g(n)=(f(All)=0)+C;f(A)=sumg-C
  rep(i,1,n+1)ans+=g[cnt[i]];
  printf("%d\n",ans.val());
  return 0;
}

总结

G

线性基的应用还是不熟

Ex

这 期望表达式, 倒着拆 去凑 函数g, 有点神奇, 学不会啊

然后这矩阵, 特别是这种接近于下三角矩阵的话, 就不需要再高斯消元什么的, 直接上就是了, 另外就是注意 mod 998244353 的除法

所以矩阵方向,也可以按照O(n^2)估计

参考

官方题解