Atcoder abc265

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
G(线段树),Ex(fft,二维卷积)

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

G - 012 Inversion

长n序列A, 元素只有0,1,2

q个询问

类型1, 输出A[l..r] 中逆序对个数

类型2, 同时 让A[l..r] 中 0->S,1->T,U->2

范围

n 1e5

q 1e5

5s

1024mb

我的思路

看起来, 就是 线段树 + 记录0,1,2个数 和逆需对个数

但是问题是, 虽然很容易计算 左侧选点 与右侧选点构成的逆需对个数

所以跨区间的容易计算

但是内部的 0,1,2 翻转 并不能只靠0,1,2个数就能得到

但如果记录 (0,1) (1,0) (0,2) (2,0) (1,2) (2,1) 个数

那么翻转就好计算了

甚至不需要记录逆对个数了, 直接统计(1,0) (2,0) (2,1) 个数即可

就过了..

代码

https://atcoder.jp/contests/abc265/submissions/35597377

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
#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 SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r

ll read(){ll r;scanf("%lld",&r);return r;}
using A3=array<ll,3>;
using A33=array<A3,3>;

struct Node{
  A3 a={0,0,0};
  A3 lazy={0,1,2}; // 未向下传递的(本层已经作用
  A33 c={{{{0,0,0}},{{0,0,0}},{{0,0,0}}}};
}seg[400010]; // seg[0] empty node
int a[100010];

template<class T>
T merge(const T&v0,const T&v1){
  T v;
  rep(i,0,3)v.a[i]=v0.a[i]+v1.a[i];
  rep(i,0,3)rep(j,0,3)v.c[i][j]=v0.c[i][j]+v1.c[i][j];
  rep(i,0,3)rep(j,0,3)if(i!=j) v.c[i][j] += v0.a[i]*v1.a[j];
  return v;
}

Node build(int o,int l,int r){
  if(l==r){
    seg[o].a[a[l]]=1;
    return seg[o];
  }
  return seg[o]=merge(build(SEG_L_CHILD),build(SEG_R_CHILD));
}

Node zotfn(int o,const A3&zot){ // zero one two
  Node newo=seg[0];
  rep(i,0,3)newo.a[zot[i]]+=seg[o].a[i];
  rep(i,0,3)newo.lazy[i] = zot[seg[o].lazy[i]];
  rep(i,0,3)rep(j,0,3)newo.c[zot[i]][zot[j]]+=seg[o].c[i][j];
  return seg[o]=newo;
}

void down(int o){
  zotfn(SEG_L,seg[o].lazy);
  zotfn(SEG_R,seg[o].lazy);
  seg[o].lazy={0,1,2};
}

Node query(int o,int l,int r,int ql,int qr){
  if(ql<=l&&r<=qr)return seg[o];
  down(o);
  return merge(
      ql<=mid?query(SEG_L_CHILD,ql,qr):seg[0],
      qr> mid?query(SEG_R_CHILD,ql,qr):seg[0]
  );
}

Node update(int o,int l,int r,int ql,int qr,const A3& zot){
  if(ql<=l&&r<=qr) return zotfn(o,zot);
  down(o);
  return seg[o]=merge(
    (ql<=mid?update(SEG_L_CHILD,ql,qr,zot):seg[SEG_L]),
    (qr> mid?update(SEG_R_CHILD,ql,qr,zot):seg[SEG_R])
  );
}

int main(){
  int n=read();
  int q=read();
  rep(i,0,n)a[i]=read();
  build(SEG_ROOT);
  while(q--){
    int op=read();
    int l=read()-1;
    int r=read()-1;
    if(op==1){
      auto x=query(SEG_ROOT,l,r).c;
      printf("%lld\n",x[1][0]+x[2][0]+x[2][1]);
    }else{
      A3 zot;
      rep(i,0,3)zot[i]=read();
      update(SEG_ROOT,l,r,zot);
    }
  }
  return 0;
}

Ex - No-capture Lance Game

h行w列

初始 每行一个向右指着的属于先手玩家, 每行一个向左指着属于后手玩家,(两个棋子不能在同一个位置,但是两个的左右关系没有限制)

交替移动一次棋子,每次 不能跨越其它棋子,至少一步,不能超过棋盘

不能移动的人输掉

现在没有棋子, 有 (W(W-1))^H 种方式放

问先手赢的局面 有多少 mod 998244353

范围

h 8000

w 30

10s

1024mb

我的思路

很像nim的游戏, 但是 前提是 向右…向左, 这样摆放, 因为这样 两个人的移动操作就是让间距减少, 两个人是”公平的”

否则的话, 两个人独立的移动步数, 且尽量希望别人无法移动, 所以贪心, 盈余步数=多的减去少的

所以问题是, 有多少个是相对运动的, 盈余是多少

显然盈余>=1的话, 那么先手必胜

盈余<=-1的话后手必胜

盈余==0 的话, 才看相对运动的

而相对运动就是nim的的游戏+sg函数

注意到对称性, 所以 2(盈余>=1 方案数) + 盈余==0 的方案数, 似乎没啥用

dp[i][j] = 前i行 先手-后手 = j 的方案数

dp[i][j+k] += dp[i-1][j] * f[k], 其中f[k] = 一行 让先后手差为k的方案数, 如果两个相向 记录到0里, f可以预先处理

所以 8000 * 8000 * 30 * 30 算出, 问题是这样似乎会tle

上 fft算转移的话, 似乎也小不了多少,

但是 考虑 实际上 dp[i][j] 表示 i次操作后 偏离j的方案数

所以考虑分治+fft, 就只需要 8000 * 30 * log()^2 的样子, 可以算

然后是 剩下相等的 部分

其实只有28个mex值,

考虑dp[i][j][xor mex] = 的方案数, 感觉很不妙啊, 和上面来说多了个xor mex值, 但好在 xor的值也就 <32

而同样的, dp[i][j][xor mex] 也表示 i次操作后,偏离=j, 异或得到xor mex的方案数

暴力 枚举xor0, xor1 去fft?

这看起来 过不了啊

= 32 * 32 * 8000 * 30 * (math.log(8000*30)/math.log(2))**2 = 78503733012.69037

难道有什么神奇的二维 fft+fwt 的方案?

题解

首先 离散傅立叶变换是

$F_k = \sum_{n=0}^{N-1} f_n W_N^{nk}$

这里从一个方向来讲

也就是 f(x) = f0+f1x+f2x^2+…+f_{N-1}x^{N-1} 看成多项式

F_k = 无非是 把 x=W^K 带入算出的, 实际上对于不同的k

f(W^{0…N-1}) 得到N-1个值, 而其实得到了N个 线性无关的方程组

所以相当于其逆矩阵 就可以反过来算(也看出是个线性变换)

$f_n = \frac{1}{N} \sum_{k=0}^{N-1} F_k W_N^{nk}$

然后FT和IFT的需要 O(NlogN)的快速过程 乘坐Fast Fourier Transform(FFT)

然后考虑说

$h_k = \sum_{i + j = k} f_i g_j.$

$f(x) = \sum_i f_i x^i, g(x) = \sum_j g_j x^j, h(x) = \sum_k h_k x^k$

有 $h(x)=f(x)g(x)$

所以 带入N个x=W^{0..N-1}

就可以得到 N个 $h(W^i)=f(W^i)g(W^i)$

这样 再做n次乘法就有了 $h(x)$的n个线性无关表达式, 再逆向

f系数 -> f(W^{0…N-1}), O(n log n)

h=fg O(n)

h(W^{0…N-1}) -> h系数, O(n log n)

然后

xor的在abc212h出现过

or/and的在abc220h出现过

dirichlet convolution abc239ex

miscellaneous: Concave Max Plus Convolution: abc218h

然后tutorial讲了一会 fft咋fast得

N=2时

$h(x)=f(x)g(x)+C(x)(x-W^0)(x-W^1) = f(x)g(x)+C(x)(x-1)(x-(-1)) = f(x)g(x) + C(x)(x^2-1)$

$h(x) = f(x) g(x) \bmod{(x^2 - 1)}$

$= (f_0 + f_1 x)(g_0 + g_1 x) \bmod{(x^2-1)}$

$= (f_0 g_0 + f_1 g_1) + (f_0 g_1 + f_1 g_0) x.$

$h(x) = f(x) g(x) + C(x)\prod_{i=0}^{N-1}(x-W_N^i) = f(x) g(x) + C(x)(x^N-1)$

$h(x) = f(x) g(x) \bmod (x^N-1)$

如何理解 mod 的部分

实际上 可以看成 $x^{i+N} \equiv x^i \pmod{x^N-1}$

$h_k = \sum_{i+j\equiv k \pmod{N}} f_ig_j$, (而一般来说, 在常见的fft中, 只是把n设置得不会被超过, 才让 没有mod发生

例如$f(x)=1+2x^2,g(x)=1+2x+3x^2$, 在 N=2的mod里

$f(x)g(x) = 1+2x+5x^2+4x^3+6x^4=5+8x+5x^2$

所以xor 可以看成 n个维度的 每个维度是长度2循环 的 FT !!!, 即Hadamard transform (Hadamard-Walsh transform)

回到本题

上面已经分析过了

k<j: (si,gi) = (0,j-k-1)

k<j: (si,gi) = ((j-1)-(W-k),0)

看成 (S,G) = (sum si,xor gi)

win = (S > 0) 并 {s=0 且 G > 0}

然后二维卷积 可以 O(hw^2 log(HW))

找了半天没找到二维相关的证明

总之还是有 A^n = ifft2d(fft2d(A).每个元素n次放) (易证)

代码

https://atcoder.jp/contests/abc265/submissions/35638390

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

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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

void fftrow(vector<vm>& a, bool rev = false) { // a[xor][plus]
  // int n = a.size(); // 2的幂次
  int m = a[0].size(); // 2的幂次
  if (rev) { // 对每一行做 ifft
    mint invm = mint{m}.inv();
    for (auto& v : a) {
      atcoder::internal::butterfly_inv(v);
      for (auto& x : v) x *= invm;
    }
  } else { // 对每一行做fft
    for (auto& v : a) atcoder::internal::butterfly(v);
  }
}

void ifftrow(vector<vm>& a){ fftrow(a,true);}

void fwtcol(vector<vm>& a, bool rev = false) { // a[xor][plus]
  int n = a.size(); // 2的幂次
  int m = a[0].size(); // 2的幂次
  mint flag=rev?mint(2).inv():1;
  rep(k,0,m){
    // FWT / IFWT
    for(int l=1;l<n;l*=2){ // len
      for (int s = 0; s < n; s += 2*l) { // start pos
        rep(i,s,s+l){ // [s..s+l) <=> [s+l..s+2l)
          mint T=a[i][k];
          mint U=a[l+i][k];
          a[i][k]   = (T+U)*flag;
          a[l+i][k] = (T-U)*flag;
        }
      }
    }
  }
}

void ifwtcol(vector<vm>&a){fwtcol(a,true);}

pair<int,int> calc(int s, int g, int W) {
  if (g < s) return {0, s - g - 1};
  return {(s - 1) - (W - g), 0};
}

int main() {
  int H=read();
  int W=read();

  int X = 1; // X 为 >=W的2的幂次
  int Y = 1; // Y 为 >=2HW的2的幂次
  while (X < W) X *= 2;
  while (Y < 2 * H * W) Y *= 2;

  auto f=vector(X, vm(Y)); // f[相向差][向左-向右 差]=方案数,如果结果非负, 则 <= H*W, 否则 负 >= H*W, 通过 % Y实现
  rep(s,1,W+1) rep(g,1,W+1) if (s != g){ /// s向左移动, g向右移动
    auto [surreal, grundy] = calc(s, g, W);
    f[grundy][(surreal+Y)%Y] ++;
  }
  fftrow(f);
  fwtcol(f);
  rep(i,0, X) rep(j,0, Y) f[i][j] = f[i][j].pow(H);// A^t = ifft( (fft(A)每项)^t)
  ifwtcol(f);
  ifftrow(f);

  mint ans = 0;
  rep(i,0, X) rep(j,0, Y / 2) if (i > 0 or j > 0) ans += f[i][j];
  printf("%d\n",ans.val());
}

总结

这场现场做了, 前面做得慢,没看G和Ex

G

有时间还是随便做的, 区间操作 太明显了

Ex

前面都想对了,没学过二维fft, 以及看了下题解,感觉又懂了一点, 以及有点fwt和fft的关系的理解的感觉

参考

官方题解

各种卷积 总结 https://noshi91.hatenablog.com/entry/2020/10/27/175112