Atcoder abc273

發表於 更新於 分類於 ， Disqus： 文章字數： 3.7k 所需閱讀時間 ≈ 12 分鐘
G(排列组合)Ex(Stern-Brocot树,树上启发式合并)

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

G - Row Column Sums 2

求个数mod 998244353

nxn的矩阵, 元素非负整数

行i 和为ri

列i 和为ci

范围

n 5000

ri,ci [0,1,2]

3s

1024mb

我的思路

这 ri, ci很有说法,

显然 sum r == sum c

说明每行/列只有4种情况 全0,1个1,2个1,1个2

而全零的行列可以直接删掉

如果是一个2的情况, 那么显然对应到另一个2的

因此变成

一些 行列为2的成对 直接填2, 剩余的 只有 1个1 和2个1

行 (a个1,b个2)

列 (c个1,d个2)

选出 t个填2的行列

sum binom(b,t) * binom(d,t) * t!(其中行定,列匹配) * f(a,b-t,c,d-t)

因为上面枚举了t

希望能在小于O(N)的时间 算出 f(a,b,c,d) = 行(a个1,b个2) 列(c个1,d个2) 全部拆成1和1+1的方案

注意到a,c 不变 考虑最小的b,d 比如f(a,b,c,0)的情况, 比较好算, = c!/(c-a)! * binom(2b,2) * binom(2b-2,2) * binom(2b-4,2) …

1
2
3
  1 1 1 1 1 1
a
b

然后考虑 每次b和d增1

1
2
3
4
  1 1 1 1 1 1 2
a             j
b
2      i      x

如果这增的两个选了, 那么4种情况

对应原来一种情况, 是原来一个(1,1) 指向的

1
2
3
4
5
6
7
  1 2
1   j
2 i x
```

对应原来一种情况, 是原来一个(1,2) 或(2,1) 指向的

1 2

2 1 j
2 i x

1
2
3
4
5
6
7
8

对应原来一种情况, 是原来一个(2,2) 指向的

````
    2 2
    1
2 1   j
2   i x

对应 [b-2][d-2] 的情况 前面还插入了两个

1
2
3
    2 2
2   1 j
2   i x

f[b][d] = f[b-1][d-1] * (a+2*(b-1)) + f[b-2][d-2] * (d-1)*(b-1)

然后考虑说 新增的没有共点 ???????????????????????????????????

1
2
3
4
      2
      1
      1
2 1 1

上面 看起来是二维, 然而实际上b和d的差为定值, 所以是个一维的

diff=d-b >= 0

f[b] = f[b-1] * (a+2*b) + f[b-2] * (b+diff-1)*(b-1)

但是不共点的情况 咋讨论啊, 感觉好多啊, 不会了

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
  1
  1
11

  1
 11
11

1 1
  1
11

1 1
 11
11

 11
  1
11

  1
1 1
11

 11
1 1
11

难道 对 这种2x2 的形态进行计数, f[i][状态=6] ?

题解

就暴力dp就完了………..

0还是直接可以移除

dp[i][j] = 前i行填完, 剩余未填列是2的个数=j 的方案数

那么对于到第i行, 显然 剩余的总个数可以计算,

1
2
 2
1x

dp[i][j] += dp[i-1][j+1] * (j+1)

1
2
 1
1x

dp[i][j] += dp[i-1][j] * (可选1)

1
2
 11
2xx

dp[i][j] += dp[i-1][j] * binom(可选1,2)

1
2
 2
2x

dp[i][j] += dp[i-1][j+1] * (j+1)

1
2
 12
2xx

dp[i][j] += dp[i-1][j+1] * (可选1) * (j+1)

1
2
 22
2xx

dp[i][j] += dp[i-1][j+2] * binom(j+2,2)

代码

https://atcoder.jp/contests/abc273/submissions/35986764

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

int R[]={0,0,0};
int C[]={0,0,0};
int main(){
  int n = read();
  rep(i,0,n)R[read()]++;
  rep(i,0,n)C[read()]++;
  if(R[1]+R[2]*2!=C[1]+C[2]*2){
    printf("0\n");
    return 0;
  }
  int c2 = C[2];
  int s=C[1]+C[2]*2; // 剩余未用点数
  vector<mint> f(c2+10,0);
  f[c2] = 1;
  auto y=[&](int j){return s-2*j;}; // j=剩余列2, s=已经用的点,c2所有列2的点, 返回剩余未用的1
  rep(t,0,R[1]){ // row = 1
    vector<mint> g(c2+10,0); // [0..c2] 减少边界判断
    rep(j,0,c2+1) g[j] += f[j+1]*(j+1); // col = 2
    rep(j,0,c2+1) g[j] += f[j]*y(j); // col = 1
    s-=1;
    rep(j,0,c2+1) if(y(j)<0) g[j]=0;
    f=g;
  }
  rep(t,0,R[2]){ // row = 2
    vector<mint> g(c2+10,0);
    rep(j,0,c2+1) g[j] += f[j+1]*(j+1); // col = 2
    rep(j,0,c2+1) g[j] += f[j+2]*((j+2)*(j+1)/2); // col = 2 2
    rep(j,0,c2+1) g[j] += f[j]*(y(j)*(y(j)-1)/2); // col = 1 1
    rep(j,0,c2+1) g[j] += f[j+1]*(j+1)*y(j+1); // col 1 2
    s-=2;
    rep(j,0,c2+1) if(y(j)<0) g[j]=0;
    f=g;
  }
  printf("%d\n",f[0].val());
  return 0;
}

Ex - Inv(0,1)ving Insert(1,0)n

$A=((0,1),(1,0))$

f(序列T) = 最小操作次数 让T所有元素 属于A, 如果没有方案则=0

每次操作 选择A中相邻的$(a,b),(c,d)$,在它们之间插入$(a+c,b+d)$

给长n的序列S, (元素两两不同)

对所有的l<=r, 求 sum f(S[l..r]) mod 998244353

范围

n 1e5

ai,bi [0,1e9]

6s

1024mb

我的思路

看每次操作对A的影响, 令 Bi= Ai.left+Ai.right

B = (1,1)

每次操作相当于 两个之间插入了和

先考虑说 单个序列的 f如何算, 上面的B似乎没有帮助

考虑二维平面, 那么相当于向量和, 而向量和的图形也就是向量平行四边行的一个对角线, 在向量之间

所以在只看夹角的情况, 每次是两个向量之间加了一个向量

也就是 (0,1) (1,0) => (0,1) (1,1) (1,0)

然后看间隔里是否有目标向量, 如果没有那么这个相邻不会再操作

如果有, 那么这个间隔一定会操作

从而找到方案

判断无法实现, 显然根据二分的思想, 一定可以让一个目标向量落在两个之间

(A)(B) 如果无法实现 目标向量

那么 从值一个偏量 上一旦大于向量 则不可能

理论上 有办法计算了

复杂度?

例如(1,1e9), 显然可达, 但是需要1e9次, 也就是 显然模拟的效率肯定不行

(A,B) 要合成 = C, 相当于解线性方程组 = 自身单独子问题

C=5A+3B = solve( (0,1),(1,0) => (5,3))

再从这个角度回到矩阵

1
2
3
4
1 0                  ? 5    5 ?
0 1                  ? 3 or 3 ?
    A = 1    B = 1 1
        1 1        1

也就是 单位矩阵 乘上 多个 A 和 B 最后得到 列向量有(5,3)的

从这个视角

就是建立一个树, 从根向下二叉, 每次就是 乘上矩阵 发展 对应的就是平面上的一个夹角, 每次询问就是 问一些点是否在树上, 且这些点到根的所有点(重复只统计一次)的点数和

这里看出 这个最少次数 看上去 没有什么意义, 就是不做无关的操作就是最小的次数

上面的只说了 当一个目标落在两个之间的不完全解决方案, 还需要有找分叉的解决方案

转化成矩阵的好处就是可以 快速幂

所以可以 直接快速幂 倍增找一个 向量是在哪个之间 从而实现分叉的查找, 同理

如果是左一下右一下, 注意到每个向量坐标和 相当于和做Fibonacci, 不会超过log次

再回到平面上

(arrow0,arrow1) 之间的一堆向量 按照夹角 排序 (j0,j1,j2,…)

计算最小幂次 能让其中产生分割, 从而这个分叉是有长度的(来让树的点还是N级别), 然后原问题变成点集到根的距离和(重复边长只计算一次)

然后 递归子问题, 从而建立树

至此 单个问题可以解决

现在问题来到 sum f(s[l..r])

变成一个和原题无关的树问题, 给一个有边长的有根树, 给点序列P

求 sum P[l..r], 中的点到根的非重距离和

感觉没法算 和

反过来, 算树上每个edge 的贡献

一条边有贡献等于它的叶向节点为根的子树里存在一个点被选

所以如果能统计每个子树被选的次数就好了

暴力算就是 子树所有点在区间上标识别

1
2
3
4
5
000010000000100000000101000111000
    5x右侧...
            8x右侧...
                     9x右侧...
                       2x右侧...

一个区间覆盖了1就被统计一次, 把覆盖了1的区间的最左1作为这个区间贡献的统计点

那上面的次数就是

如果两个不重叠1的合并

1
2
0010000100000
0000101001000

唯一知道的就是个数会变多, 但又比两个的和小, 相当于 去掉重复统计的部分

干 树和区间不会

题解

好 也是建树, 根为[0/1,1/0], 每个树两个节点

这叫做 Stern-Brocot树, 有 点(p,q) 互质 等价于 在树上

题意转化, 和我想的一样 就是求树上需要多少节点/路径 能覆盖指定 S[l..r]对应的节点

直接想 也是 通过判断相等/在左侧/在右侧 递归向下

哈哈 也是想到(1e9,1) 这种 需要1e9, 特殊点的方向都想的一样的

哦这里没有用矩阵, 而是直接代数上 考虑 (a+kc)/(b+kd), emmmmm 很有道理 因为毕竟上面矩阵的快速幂 等价其实也就是这个

啊?????? 啥 就可以解了?

省略了的 刚好是我不会的 艹了……………………

怎么计算内

还是上面那样, 然后树上合并的时候 用启发式, 每次把小的向大的中1个一个合并

Stern-Brocot树

根[0/1,1/0]

节点[a/b,c/d]的两个子节点[a/b,(a+c)/(b+d)],[(a+c)/(b+d),c/d]

性质:

每一层单调递增(对应二维平面射线显然)

上面只有简分数: 所有a/b,c/d 都是最简分数(分子分母没有公约数) 根据上面的矩阵 知 矩阵的 行列式 始终为1, (|AB|=|A||B|) 所以 不会有公约数

所以 说明如果点(p,q)要在树上 那么p,q 互质才有可能

任何最简分数在树上:

假设在左侧 a/b < p/q < c/d => a/b < p/q < (a+c)/(b+d)

考虑矩阵运算与行列式

1
2
3
4
5
c p
d q = cq-pd >= 1

p a
q b = pb-aq >= 1

若小于(不等于)

1
2
a+c p   c p   a p   c p   p a   c p
b+d q = d q + b q = d q - q b < d q

一句话就是 一侧行列式值不变, 一侧行列式值单调递减 且均为正整数, 有理数离散, 不可能一直减, 所以 ‘若小于’会在有限次内不成立, 变成等于

综上 充分必要

代码

https://atcoder.jp/contests/abc273/submissions/36005069

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
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;}
using vec=std::pair<ll,ll>; // 二维向量,分数

bool operator<(const vec&f0,const vec&f1){ // 夹角比较
  return f0.first*f1.second < f1.first*f0.second;
}
// bool operator>(const vec&f0,const vec&f1){ // 夹角比较
//   return f0.first*f1.second > f1.first*f0.second;
// }
vec operator+(const vec&f0,const vec&f1){ // 向量和
  return {f0.first+f1.first,f0.second+f1.second};
}
vec operator*(const vec&f0,const int&k){ // 向量 数量积
  return {k*f0.first,k*f0.second};
}

vector<pair<vec,ll>> vp; // {{x,y},idx} 只放可能的
set<ll> wall; // 隔断的S的index
set<ll> vst[100010]; // vst[树节点} = 点下标集合
mint cnt[100010]; // cnt[u] = 树上点u被区间覆盖计数
const int TMP=100005;

// dst <- src ( r向l 合并, 如果大小不满足, 先交换再合并)
// src.clear(); (清空src)
void merge(int dst,int src,bool init=false/* 用在初始时一侧为空的时候 计算代价 */){
  if(dst==src)return;
  if(dst<0 || src<0)return;
  if(vst[dst].empty() && vst[src].empty())return;
  if((!init) && vst[dst].size()<vst[src].size()){ // 启发式 小向大, sum_轻儿子 = O(N log N)
    swap(vst[dst],vst[src]);
    swap(cnt[dst],cnt[src]);
  }
  for(auto &nx : vst[src]){
    auto it=wall.lower_bound(nx); // 通过不可选计算区间
    ll rs=*it;
    ll ls=*prev(it); // index区间 (ls...rs)
    it=vst[dst].lower_bound(nx);
    if(it!=vst[dst].end())   rs=min(rs,*it);
    if(it!=vst[dst].begin()) ls=max(ls,*prev(it));
    cnt[dst]+=(nx-ls)*(rs-nx); // [ls...nx...rs]
    vst[dst].insert(nx);
  }
  vst[src].clear();
  cnt[src]=0;
}

ll height(vec l, vec r,vec del,int side){
  ll lh=1,rh=2e9; // c++20 iota_view + lower_bound
  while(lh<=rh){
    ll mh=(lh+rh)/2;
    vec nl,nr;
    if(side==0){ // l < r < del, 已知 l+del < r 求max(h), 使 l+h*del < r
      nl=l+del*mh;
      nr=r;
    } else { // del  < l  < r, 已知 l < del+r, 求max(h), 使 l < del*h+r
      nl=l;
      nr=r+del*mh;
    }
    if(max({nl.first,nl.second,nr.first,nr.second})>1e9){ // 过大
      rh=mh-1;
      continue;
    } // too low
    if(nl<nr) lh=mh+1;
    else rh=mh-1;
  }
  return rh; // rh+1==lh [1...rh 满足][lh.... 不满足
}

mint res=0;

int sbtree(int l,int r,vec lp,vec rp,int w=1/*节点权重*/){// vp[l..r] 左向量lp < 右向量rp, 返回树的根的index
  if(l>r)return -1;
  vec mp=lp+rp; // 向量和
  // [l,pos-1] < mp <= [pos,r]
  int pos=(int)(lower_bound(vp.begin()+l,vp.begin()+r+1,mp,[](const auto&vpitem,const auto&searchv){
     return vpitem.first < searchv;
  }) - vp.begin());
  int mr=pos-1,ml=pos; // [l,mr] [ml,r]
  int key=-1; // 分割向量index, 用作树的index
  if(ml<=r && mp==vp[ml].first) { // 分割向量 在S中
    key = vp[ml++].second; // 在S的划分中 移除它 [l,mr=bl-1] [ml=bl+1,r]
    vst[TMP].insert(key); // 主要是复用merge逻辑 先放tmp再merge进key
    merge(key,TMP,true);
  }

  int lk=-1,rk=-1; // l key, r key
  if(mr==r){ // 全在左侧 lp < [l..mr=r] < mp < rp, 一次不够分割, 如果左右交替 则febnacci不会超过log次
    ll h=height(vp[r].first,rp,lp,1); // 快速计算幂次
    lk=sbtree(l,mr,lp,lp*h+rp,h);
  } else if(ml==l){ // 全在右侧 lp < mp < [l=ml..r] < rp
    ll h=height(lp,vp[l].first,rp,0); // 快速计算幂次
    rk=sbtree(ml,r,lp+rp*h,rp,h);
  } else { // 每发生一次数组分裂, 最多n次
    lk=sbtree(l,mr,lp,mp);
    rk=sbtree(ml,r,mp,rp);
  }

  int root=max({key,lk,rk}); // 非-1的 都可以作为 根的index, 至少有一个
  for(auto k:{key,lk,rk}) merge(root,k);
  res+=cnt[root]*w;
  return root;
}

int main(){
  int n=read();
  rep(i,0,n){
    ll a=read();
    ll b=read();
    if(a+b==1)continue; // (0,1)(1,0)不消耗次数
    else if(gcd(a,b)==1)vp.push_back({{a,b},i});
    else wall.insert(i); // 一定不再的点产生切割
  }
  wall.insert(-1);
  wall.insert(n);
  // 默认的sort 用的是自己和其它的operator<(other), 而不是两两比较的operator<(v0,v1)
  sort(vp.begin(),vp.end(),[](const auto&l, const auto&r){return l.first<r.first;});

  if(vp.size()) sbtree(0,vp.size()-1,{0,1},{1,0});
  printf("%d\n",res.val());
  return 0;
}

总结

G

好吧 我好想把题想复杂了, 连最直接的都没想

应该不要过早想优化和提取? 先试试直接的, 抑制一下见到就想开始简化的冲动

Ex

gcd想了一半, 没推下去, 按理说应该要能想到 互质等价的… 唉

但除了存在性的部分还是自己想出来了, 而且本身是倍增查找,即使没有存在性 也可以算出是否存在

好 我不会的部分好像又是重轻儿子 和启发式合并的部分……… 总之就是 sum S_轻儿子 = O(N log N)

参考

官方题解

https://tjkendev.github.io/procon-library/python/math/stern-brocot-tree.html