Atcoder abc278

發表於 2022-11-19 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 5.8k 所需閱讀時間 ≈ 19 分鐘

G(Grundy's number)Ex(q-analog,stirling,排列组合,stirling反演)

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

G - Generalized Subtraction Game

1..n 在桌子上, 给定l,r

每次选 [x…x+len-1], 要保证这一段目前都存在, 且 len \in [l..r], 然后移除被选的段

范围

n 2000

1024mb

我的思路

这n一眼是个n^2 的样子

但感觉可以搞事情, 如果第一次把整个砍成两个相等段, 那么直接对称操作, 就保证先手必胜了?

那么问题就在于有没有可能, 因为 l==r 时有可能砍的至少会差1

所以问题变成, 如果l < r, 那么先手总可以从中间剖成两段对称操作win

如果 l==r ,那么每次选的都是定长, 问题变成f[len] 的操作次数

这怎么搞?

只能想到说, 比如 n = 3l-1 时先手怎么都是输, 因为剩下的有且只有一个 [l,2l-1) 之间

但是再往更长?

看起来可以sg函数, 但总觉得这状态也太多了, 如何n^2 表示?

题解

也是先考虑切半, 然后对称操作

…. 好家伙, 直接说l==r 时用 Grundy’s number 做, 没说细节

看了下snuke的代码, 似乎用了递归的意义,

单个长度, 和两个长度都是图中的点, 那么递归思想, 计算单个i的时候, 比它小的都计算完了

其实问题就在于两个长度 (l0,l1) 的 sg中的值是多少, 而这最简单就是

(l0,l1,l2,l3…)

和

((l0,l1),l2,l3,…) 是等价的

所以 (l0,l1) 的sg值就是sg[l0]^sg[l1](!!!!!!)

所以其实只需要计算每个的sg 就行

代码

https://atcoder.jp/contests/abc278/submissions/36726288

#include <bits/stdc++.h>
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;}

void o(int st,int len){
  printf("%d %d\n",st,len);
  fflush(stdout);
}

void o(const char *s){
  printf("%s\n",s);
  fflush(stdout);
}

int n,l,r;

void Grundy() {
  vector<int> dp(n+1); // dp[0..n] = 0 Grundy's number
  rep(i,1,n+1) { // 枚举长度
    vector<bool> s(i+1); // s[0..i] = 0
    rep(j,0,i-l+1) s[dp[j]^dp[i-l-j]] = true; // 计算它的所有拆分的 xor
    while (s[dp[i]]) dp[i]++; // mex
  }
  vector<int> a(n,1); // [0...n) = 1, [n] = 0, 0-index 表示 剩余的点
  a.push_back(0);
  auto fil = [&](int x, int y) { fill(&a[x],&a[x+y],0); }; // a[x..x+y-1] = 0
  auto f = [&]() {
    vector<pair<int,int> > ls; // {len, start idx}
    int now = 0; // 当前连续的长度
    int x = 0; // 所有连续段 的 grundy xor
    int si = 0; // 起始的位置
    rep(i,0,n+1) {
      if (a[i]) { // 为1
        ++now;
      }else { // 为 0
        if (now) {
          ls.push_back({now,si});
          x ^= dp[now];
        }
        now = 0;
        si = i+1;
      }
    }
    for (auto [w,si]: ls) rep(j,0,w-l+1) if((x^dp[w]^dp[j]^dp[w-l-j]) == 0){// 枚举位置 一定存在一个方案 成立, 注意运算优先级加括号
      o(si+j+1,l);
      fil(si+j,l);
      return;
    }
  };
  if (dp[n]) {
    o("First");
    f();
  } else {
    o("Second");
  }
  while (1) {
    int x=read();
    int y=read();
    if (x <= 0) break;
    fil(x-1,y);
    f();
  }
}

int main() {
  n=read();
  l=read();
  r=read();
  if (l == r) {
    Grundy();
  } else { // 对称就完事
    o("First");
    for(int w:{l,l+1}) if ((n-w)%2 == 0) {
      int i = (n-w)/2+1; // [1..i-1][i...i+w-1][i+w..n]
      o(i,w);
      i += w-1; // [1..i-1] 与 [i+w..n] 的偏移量
      while (1) {
        int x=read();
        int y=read();
        if (x <= 0) break;
        x += (x<i)?i:-i;
        o(x,y);
      }
      break;
    }
  }
  return 0;
}

Ex - make 1

非负序列是好序列, 当且进当存在子序列的元素xor =1

arr=空序列

每次$[0,2^b)$, 中选一个未被选择的数放入arr尾部, 直到arr为好序列

求恰好长n的序列有多少个, $\bmod 998244353$

范围

n 2e5

b 1e7

1024 mb

我的思路

换据话说, 就是前面 n-1个都不满足, 而第n个满足

这个b和n的范围, 感觉有O(n log n) O(b) 这类, 如果是n相关, 那么b可能就要数学公式里或者log b见了,

然后 xor = 1 是什么意思呢

就是高位 xor = 0, 同时末位 xor != 0

如果是xor == 0 的话, 那么有任意不同组的 xor 不一样(以前某场遇到过)

但是此题可能是有xor == 0 的存在, 比如

(2,4,6,8,16,24)

感觉是末位是1 的高位有几种, 末位是0 的高位所有xor的结果有几种

但问题是比如选了个末位是0 的, 更新状态也是问题

显然 (偶数) 与 (偶数+1), 只能选1个

题解

令

$F(s) = $长$s$的非好序列的个数

$G(s) = $长$s$的非好序列的个数(但可以重复取)

$ans = good(N) - good(N-1)\cdot(2^B-N+1)$ 即恰好=N的好序列, 可以变化成长N的好序列 - 长N-1的好序列第n个随便选(乘 $(2^B - N + 1)$)

(注意到 xor=1定义为好序列的话, 非好序列中同一个值选多次依然是非好)

$G(s) = \sum_{t=0}^s {s \brace t} F(t)$, 其中 ${s \brace t}$ 是长s的序列只有t个不同值的方案数 (https://en.wikipedia.org/wiki/Stirling_transform

这样的话可以反演$F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brack t} G(t).$ , Stirling 反演

然后如何算G (这就和CF1603F 一样了)

$G(s) = \sum_{r=0}^s ((\prod_{i=1}^{r} (2^B-2^i)) \binom{s}{r}_ 2)$

$= \sum_{r=0}^s (2^{\binom{r}{2}} (\prod_{i=1}^{r} (2^{B-i}-1)) \binom{s}{r}_ 2)$

$= \sum_{r=0}^s (2^{\binom{r}{2}} (\prod_{i=1}^{r} \frac{2^{B-i}-1}{2-1}) \binom{s}{r}_ 2)$

$= \sum_{r=0}^s (2^{\binom{r}{2}} (\frac{\lbrack B-1 \rbrack_ 2 !}{\lbrack B-1-r \rbrack_ 2 !}) \binom{s}{r}_ 2)$

$= \lbrack \mathbf{B-1}\rbrack_ 2 ! \lbrack \mathbf{s}\rbrack_ 2 ! \sum_{r=0}^s \left( \frac{2^{\frac{r(r+1)}{2}} }{ \lbrack \mathbf{B-1-r}\rbrack_ 2 ! \lbrack \mathbf{r}\rbrack_ 2 ! \lbrack \mathbf{s-r} \rbrack_ 2 !}\right)$

这样的话需要$O(n^2)$ 算, 但是注意到右边可以拆成 $G(s) =C \sum_i h_0(i)h_1(s-i) $ 也就是标准的卷积形式了(C为与s,i无关的常数)

Stirling 反演

stirling

$\displaystyle f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\ k \end{Bmatrix}g(k) \Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\ k \end{bmatrix}f(k)$

反演

直接正确性的话,无论是带入证明还是证明两个矩阵相乘是单位矩阵(

$\displaystyle \sum_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]$ 和 $\sum_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\ k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]$)

q-analog (q-模拟)

在引入一个新的参数q后当q→1时原定理、等式或表达式的极限)

在数学里，尤其是组合数学和特殊函数领域，一个定理、等式或者表达式的q-模拟是指在引入一个新的参数q后当q→1时原定理、等式或表达式的极限。最早地研究得较为深入的q-模拟是 19世纪被引入的基本超几何级数。

q-模拟在包括分形、多重分形, 混沌动力系统的熵表达在内的多个研究领域都有应用。另外，在量子群和 q-变形代数的研究中也有应用。

“经典” q-模拟开始于莱昂哈德·欧拉的研究工作，后来由F. H. Jackson 以及其他人所扩展。

q-number

定义一个自然数$n$的$q$模拟为$1+q^1+q^2+\ldots+q^{n-1}=\dfrac{1-q^n}{1-q}$

记作$\lbrack n\rbrack_q$ (是个关于q的多项式)

这样在q趋于1时, 表达式趋近于n

q-factorial (q阶乘)

类似的 $\prod_{i=1}^n \lbrack i\rbrack_q = \lbrack n \rbrack_q !$ 显然是用来 q趋于1时整个趋于 $n!$

有特点 $\sum_{p\in S_n}x^{inv(p)}=\prod_{i=0}^n(1+x+x^2\cdots x^i)=\lbrack n\rbrack_x!$

其中 $S_n$ 表示$n$个数的全排列, $p$表示一个具体排列, inv表示排列中的逆序对个数

证明: 直接通过意义就可以证明, 第i项中的$x^j$ 乘出来对应的意义是 i, 作为逆序对构成左侧有j个, 因为当知道每个值作为左侧有多少个时, 那么就对应了一个具体的p, 而p之间两两不同, 覆盖了所有 i 选则[0..i-1] 的所有组合

注意 inv() 与 maj() 有相同的分布

MacMahon 研究了 1,…,n 的可重集合, 的major index和= 成对的数中第一个大于第二个, 第一个的下标

如 major index(4,3,1,2) = 1+2 = 3 , inv(4,3,1,2) = 5

如 major index(4,1,3,2) = 1+3 = 4 , inv(4,1,3,2) = 4

排列	inv	major index
123	0	0
132	1	2
213	1	1
231	2	2
312	2	1
321	3	3

MacMahon 证明了 inv和major有相同的生成函数 TODO ??????

q-binomial (q二项式)

一样的想法, 就是所有原来的值, 换成q-模拟的

$\dbinom{n}{k}_ q=\dfrac{\lbrack n\rbrack_ q!}{\lbrack k\rbrack_ q!\lbrack n-k\rbrack_ q!} = \frac{\prod_{i=n-k+1}^{n} \lbrack i\rbrack_ q}{\prod_{i=1}^k\lbrack i \rbrack_ q}$

表示的是可重集合 {k个0, n-k个1}的全排列逆序对生成函数 TODO??????

例如 0011010011 是 {5个0, 5个1} 的一个具体排列, inv(0011010011) = 3+3+2 = 8

$\sum_{p\in S_{k,n-k}}\ q^{inv(p)}=\dbinom{n}{k}_ q$

根据定义显然$\binom{n}{k}_ q =\binom{n}{n-k}_ q$

二项式 $\prod_{i=0}^{n}\frac{1}{1-q^ix} = \sum_{i \ge 0} x^i \binom{i+n}{n}_ q$

证明:数学归纳

$F = \sum_{i \ge 0} x^i \binom{i+n}{n}_ q$

$= \sum_{i \ge 0} x^i \binom{i+n-1}{n-1}_ q + q^n \sum_{i \ge 0} x^{i} \binom{i+n-1}{n}_ q$

$= \sum_{i \ge 0} x^i \binom{i+n-1}{n-1}_ q + q^n x \sum_{i \ge 0} x^{i} \binom{i+n}{n}_ q$

$= \frac{1}{\prod_{i=0}^{n-1} (1-q^ix)} + q^n x F$

$F = \frac{1}{1 - q^nx} \prod_{i=0}^{n - 1} \frac{1}{(1-q^ix)} = \prod_{i=0}^{n} \frac{1}{(1-q^ix)}$

子空间计数(typical)

事实上，q-二项式系数与向量空间的组合学有关。作为一个代表性的例子，考虑如何计算子空间的数量。

$q$是任意质数(如果$q=4$ 有$2(2,2)=(0,0)$), $n$维向量空间 $\mathbb{F}_ q^n$ (mod q的线性空间(一般我们常用的是没有mod和mod2的))

$\mathbb{F}_ q^n$ 的 $r$维子空间的数量为$\binom{\mathbf{n}}{\mathbf{r}}_ q$

令$a_{n, r} = $ 在$\mathbb{F}_ q^n$ 中的 $r$维子空间数, 要证明 $a_{n,r} = \dbinom{n}{r}_ q$

令$f(n,r)$ 表示 , $n$维向量空间中 $r$维子向量空间的基向量的序列(因为是序列,所以是有序的)

有$a_{n, r} \times f(r, r) = f(n, r)$ ($a$是无序的, 而$f$是有序的, 就需要乘上$f(r,r)$内部排序(对应的也像排列组合里建立排列和组合的关系的 $r!$ 一样)

这里是 $f(n,r)$ 是从n维空间取r维的基, 第一个 $q^n-1$ 个取法, 第二个$q^n-q$个取法(要和前面的线性无关)

$a_{n,r} = \frac{f(n,r)}{f(r,r)} $

$= \frac{(q^n-1)(q^n-q)\cdots(q^n-q^{r-1})}{(q^r-1)(q^r-q)\cdots(q^n-q^{r-1})} $

$= \frac{(q^n-1)(q^{n-1}-1)\cdots(q^{n-(r-1)}-1)}{(q^r-1)(q^{r-1}-1)\cdots(q-1)} $

$= \frac{\frac{q^n-1}{q-1}\frac{q^{n-1}-1}{q-1}\cdots\frac{q^{n-(r-1)}-1}{q-1}}{\frac{q^r-1}{q-1}\frac{q^{r-1}-1}{q-1}\cdots\frac{q-1}{q-1}} $

$= \frac{\lbrack n \rbrack_ q\lbrack n-1 \rbrack_ q\cdots\lbrack n-(r-1) \rbrack_ q}{\lbrack r \rbrack_ q\lbrack r-1 \rbrack_ q\cdots\lbrack 1 \rbrack_ q}$

$= \binom{n}{r}_ q$ 得证

关于$f(n,r)$

首先$q=2$ 时就是常见的 (0/1,0/1,…)的xor, 第一次 $2^n-1$种,第二次$2^n-2$种,第三次$2^n-2^2$种,…

这里我一直没理解 $q\neq 2$ 的时候, 在想比如$q=3$的时候怎么解释

而$q=3,n=2$即$\mathbb{F}_ 3^2$ 可选基向量有$(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)$ (mod 3的 xor)

加法运算 $(a_0,a_1) + (b_0,b_1) = ((a_0+b_0)\bmod 3,(a_1+b_1)\bmod 3)$

例如 $(1,1)$ 和 $(2,2)$ 线性相关(正常的线性代数), $(2,1)$ 和$(1,2)$线性相关(在$\bmod 3$下),

注意的是, 虽然$(1,1)$ 和$(2,2)$ 线性相关, 但是这两个选择是不同的基向量选择方案, 所以第一次选择方案数依然是$q^n-1$, 第二次选择依然是$q^n-q$ …

二项式递推

要证明 $\binom{\mathbf{n}}{\mathbf{r}}_ q = q^{n-r} \binom{\mathbf{n-1}}{\mathbf{r-1}}_ q + \binom{\mathbf{n-1}}{\mathbf{r}}_ q = \binom{\mathbf{n-1}}{\mathbf{r-1}}_ q + q^r \binom{\mathbf{n-1}}{\mathbf{r}}_ q$

对于空间中向量$v$, 定义$top(v)$ 表示向量中最大非零的维度下标

例如$\mathbb{F}_ 3^4$ 中,$top((2,1,2,0)) = 3,top((0,2,0,0)) = 2$

然后$r$维的空间 一一映射 到 (大小为$r$个向量组 $b$), 其中$b$ 满足

$top(b_i)$ 单调递增
$b_i$的第 $top(b_i)$是$1$
不同的$i < j$, 在$b_j$ 中, 第 $i$ 位是0

例如$\mathbb{F}_ 3^4$ 中一个$r=2$的空间

1 2	(0,1,2,0) (1,2,0,0)

那么它对应的b是

第二条性质, 最高位为1, 每个向量乘上最高位关于q的乘法模拟元
(0,1,2,0) x 2 = (0,2,1,0)
(1,2,0,0) x 2 = (2,1,0,0)
第三条性质, 化为阶梯形
(0,2,1,0) + (2,1,0,0) = (2,0,1,0)
第一条性质, 所以b为
(2,1,0,0)
(2,0,1,0)

注: 转化后的基向量组$b$ 和转化前的基向量组对应的是同一个空间, 也就是在$a_{n,r}$ 中它们的贡献是用一次

那么就是考虑 $b$ 的计数,

考虑$top(b_r) \neq n$ 也就是最高的非零位也不是$n$, 那么这样的向量组就和$n-1$里一样, 就是$a_{n-1,r}$

考虑$top(b_r) = n$, 也就是最后一个向量最高非零位是第$n$位, 注意到有限制, $b_r$的其它向量的最高位都要是$0$, 所以剩下自由填写的有$(n-1) - (r-1) = n-r$ 也就是$q^{n-r}$, 而$b_{1..r-1}$ 就对应$n-1$维度下的大小为$r-1$的向量组$b$

$a_{n, r} = q^{n-r} a_{n-1, r-1} + a_{n-1, r}$

换回去就证明了

$\binom{\mathbf{n}}{\mathbf{r}}_ q = q^{n-r} \binom{\mathbf{n-1}}{\mathbf{r-1}}_ q + \binom{\mathbf{n-1}}{\mathbf{r}}_ q.$

代数证明另外一半

代数证明就很无脑了, 简单快捷, 反而这意义证明, 让我绕了半天在大佬点拨无数次以后才理解

$\binom{n}{k}_ {q}-\binom{n-1}{k-1}_ {q}$

$=(\frac{q^{n}-1}{q^{k}-1}-1) \binom{n-1}{k-1}_ {q} $

$=q^{k}(\frac{q^{n-k}-1}{q^{k}-1}) \binom{n-1}{k-1}_ {q} $

$= q^{k} \binom{n}{k-1}_ {q} $

生成函数 $\prod_{i=1}^{n-1} (q^i x + 1) = \sum_{r=0}^n q^{\binom{r}{2}} \binom{n}{r}_ q x^r$

也就是要证明 $a_{n, r} = \binom{n}{r}_ q = q^{-r(r+1)/2} \lbrack x^r \rbrack \prod_{i=1}^{n} (q^i x + 1);$

令 $b_{n,r} = a_{n,r} q^{r(r-1)/2}$ 和 $f_n(x) =\sum_{r} b_{n,r} x^r = \prod_{i=1}^{n} (q^i x + 1)$

则有 $f_n(x) (q^{n+1} x + 1) = f_n (qx) (qx + 1),$, 相当于所有x的地方变成qx, 而x每个地方都是1次

对比第$r$项的系数,有

$q^{n+1} b_{n,r-1} + b_{n,r} = q^r (b_{n,r-1} + b_{n,r}) $

即 $b_{n,r} = \frac{q^r - q^{n+1}}{1-q^r}b_{n,r-1} = \frac{(q^1 - q^{n+1}) \cdots (q^r - q^{n+1})}{(1-q^1) \cdots (1-q^r)} = q^{r(r-1)/2} \binom{n}{r}$

归纳证明: 其实这里直接对 $\prod_{i=1}^{n-1} (q^i x + 1) = \sum_{r=0}^n q^{\binom{r}{2}} \binom{n}{r}_ q x^r $ 左侧n归纳证明更容易(注意r的加减号和n与n-1) 简单无脑

代码

https://atcoder.jp/contests/abc278/submissions/36767147

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
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++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;}
const int N = 10000000;
mint nq2[N+10]={0}; // n_{q=2}, q-number n, nq2[i]=1+q^1+q^2+..+q^i, q=2, nq2[i]=2**i-1
mint facq2[N+10]={1}; // fac_{q=2}, q-factor n, = nq2[0]*nq[1]*...*nq2[i]
mint ifacq2[N+10]; // ifac[i] = 1/facq[i]

int main(){
  int n=read(); // 2e5
  int b=read(); // 1e7
  rep(i,1,N+1) nq2[i] = nq2[i-1]*2+1;
  rep(i,1,N+1) facq2[i] = facq2[i-1]*nq2[i];
  ifacq2[N] = facq2[N].inv();
  per(i,0,N) ifacq2[i]=ifacq2[i+1]*nq2[i+1];
  // G(s) = \lbrack \mathbf{B-1}\rbrack_ 2 ! \lbrack \mathbf{s}\rbrack_ 2 ! \sum_{r=0}^s \left( \frac{2^{\frac{r(r+1)}{2}} }{ \lbrack \mathbf{B-1-r}\rbrack_ 2 ! \lbrack \mathbf{r}\rbrack_ 2 !}\right)\left(\frac{1}{\lbrack \mathbf{s-r} \rbrack_ 2 !}\right)
  vector<mint> h0(n+1);
  rep(i,0,min(n+1,b)) h0[i] = mint(2).pow((long long)i*(i+1)/2) * ifacq2[b-1-i] * ifacq2[i];
  vector<mint> h1(n+1);
  rep(i,0,n+1) h1[i] = ifacq2[i];
  vector<mint> g=atcoder::convolution(h0,h1);
  rep(i,0,n+1) g[i] *= facq2[b-1]*facq2[i];

  // Stirling 反演
  // F(n) = \sum_{t=0}^n (-1)^{n-t} {n \brack t} G(t).
  vector<vector<mint> > stirling1 = {{1}}; // 第一类stirling数 f_n = \prod_{i=0}^{n-1} (i+x), 注意会有n=1的时候
  rep(i,0,n-1) stirling1.push_back({i,1});
  // stirling f_{n-1}
  while(stirling1.size()>1){ // 分治
    rep(i,0,stirling1.size()/2) stirling1[i] = atcoder::convolution(stirling1[i*2],stirling1[i*2+1]);
    if(stirling1.size()&1) stirling1[stirling1.size()/2] = stirling1.back();
    stirling1.erase(stirling1.begin()+(stirling1.size()+1)/2,stirling1.end());
  }
  auto f=[&](int n){
    mint v = 0;
    rep(i,0,n+1) v+= mint(-1).pow((n-i)%2) * stirling1[0][i] * g[i];
    return v;
  };
  mint twob=mint(2).pow(b); // 2**b
  mint good_n_1 = 1;
  rep(i,0,n-1) good_n_1*=(twob-i);
  mint good_n = good_n_1*(twob-(n-1));
  good_n_1-=f(n-1);
  stirling1[0]=atcoder::convolution(stirling1[0],{n-1,1}); // stirling f_{n}
  good_n -= f(n);
  printf("%d\n",(good_n-good_n_1*(twob-n+1)).val());
  return 0;
}

CF 1603F October 18, 2017

给 $n(10^9), k(10^7), x$

问多少序列 a[1..n] 满足任意非空子序列的 xor 都不为x

其中 $a[i] \in [0,2^k)$

个数 $\bmod 998244353$

$x \in [0,20]$

512mb

题解

$x=0$ 时, 很简单, 就是n个线性无关的向量构成线性空间

$= (2^k-1)(2^{k}-2)(2^k-2^{2})(2^k-2^{3})\cdots(2^k-2^{n-1})$

注: 这里和 atcoder 里tutorial中的子空间计数的f表达式一样, 只是p=2 (依然没有搞懂如果p!=2 这个f的表达式如何理解, 还是说子空间计数就是需要p=2)

x!=0时

类似的, 先考虑r个线性无关的向量, 第一个向量不能是 0和x, (2^k-2)

第二个有4个不能选, (2^k-4), (0,x,v0,x^v0)

第三个有8个不能选, (2^k-8), (0,x,x0,x^v0,v1)

… (换句话说, x与这r个线性无关的向量构成了r+1 个线性无关的向量

所以其实和x具体大小无关, 都是一样的个数

所以方案数 = (2^k-2)(2^k-4)(2^k-8) …, r个乘积项

然后是要一一对应的统计, 一共是n个向量

那么就是选的r个位置, 每个的前面都不能表示它来作为标识

然后就是插入和前面线性相关的向量,

第一个前面可以插入的只有1种(0), 写生成函数就是 $1+x+x^2+\cdots=\frac{1}{1-x}$

第一个和第二之间可以插入的只有2种(0,x), 写生成函数就是 $1+2x+4x^2+\cdots=\frac{1}{1-2x}$

第二个和第三之间可以插入的只有4种(0,x,v0,x^v0), 写生成函数就是 $1+4x+16x^2+\cdots=\frac{1}{1-4x}$

一共插入 n-r个 ,所以就是$x^{n-r}$ 的系数 $\displaystyle [x^{n-r}] \prod_{i=0}^r \dfrac{1}{1-2^ix}=\displaystyle [x^{n-r}] \sum_{i\ge 0} x^i \binom{i+r}{r}_ 2 = \binom{(n-r)+r}{r}_ 2$

所以方案 $\sum_{r=0}^n ((\prod_{i=1}^{r} (2^k-2^i)) \binom{n}{r}_ 2)$

总结

对称操作想得到, 但是Grundy’s number 还是不熟

之前 SG 只学会说每个独立游戏算状态mex, 然后xor 等价 nim, 而这种有点递归感觉的第一次遇到

位运算计算优先级比 == 低, 还是无脑加括号好

等于的恰好变成, 不一定恰好的相减

这tutorial 感觉各种神奇的东西, 但是 q=1时也成立, 我也不懂究竟是有我没理解到的地方还是真的笔误

q-analog

这感觉数学推通很容易, 但是按照各种举例的意义作为推通的桥梁反而很难, 不如推通后直接用

n的q模拟 $\lbrack n\rbrack_q = \sum_{i=0}^{n-1} q^i = \frac{1-q^n}{1-q}$

q阶乘定义 $\lbrack n \rbrack_q ! = \prod_{i=1}^n \lbrack i\rbrack_q$, 性质: 关于全排列 $\sum_{p\in S_n}x^{inv(p)}=\lbrack n\rbrack_x!$

q二项式 $\dbinom{n}{k}_ q=\dfrac{\lbrack n\rbrack_ q!}{\lbrack k\rbrack_ q!\lbrack n-k\rbrack_ q!}$, 性质: 关于可重集合全排列 $\sum_{p\in S_{k,n-k}}\ q^{inv(p)}=\dbinom{n}{k}_ q$

$\binom{n}{m_1,m_2,\cdots,m_k}=\frac{[n]_ {q} !}{[m_1]_ {q} ![m_2]_ {q} !\cdots [m_k]_ {q} !}$

显然$\binom{n}{k}_ q =\binom{n}{n-k}_ q$

$\binom{\mathbf{n}}{\mathbf{k}}_ q = q^{n-k} \binom{\mathbf{n-1}}{\mathbf{k-1}}_ q + \binom{\mathbf{n-1}}{\mathbf{k}}_ q = \binom{\mathbf{n-1}}{\mathbf{k-1}}_ q + q^k \binom{\mathbf{n-1}}{\mathbf{k}}_ q$

$\prod_{i=0}^{n-1} (1+q^ix) = \sum\limits_{i=0}^n q^{\binom{i}{2}} {n \brack i}_ q x^i$

$\prod_{i=0}^n \frac{1}{(1-q^ix)} = \sum_{i \ge 0} x^i \binom{i+n}{n}_ q$

q-Vandermorde $\binom{n + m}{k}_ q = \sum_{i=0}^k q^{(n-i)(k-i)} \binom{n}{i}_ q \binom{m}{k-i}_ q$

$\mathbb{F}_ q^n$意思是 n 维的模 q(q是质数)意义下的空间 , 向量数是$q^n$

所以说起来, q模拟更像是 q趋于1时的很多经典表达式成立,所以采取的传统写法加个下标q, 而实际使用的是q不为1时一些统计, 而这些东西, 如果不关心q模拟, 直接去做数学推反而更简单emmmmmm,

然后就是Stirling反演, 又对反演懂了一点