ARC147F
lsj2009
·
·
题解
Description
求长度为 n 且字符集为 \{\tt A,\tt B,\tt C\}，满足如下条件的的字符串 S 数量：
- 设 C_{i,\tt A},C_{i,\tt B},C_{i,\tt C} 分别为字符串 S_{[1,i]} 中 \tt A,\tt B,\tt C 的出现次数，则对于任意 1\le i\le n 有：
答案对 \mathbf{2} 取模。
## Solution
### Part 1
**这一部分的转换对于四次方做法并不是必要的，但对于后面是有极强的提示性的。**
考虑 $i\to i+1$ 的增量，也就是我最初有三个分别等于 $X,Y,Z$ 的变量，每次操作会有 **一个加一，一个减一**，且这三个变量 **始终非负**。
更具象的刻画是：
- 存在一个长度为 $X+Y+Z+3$ 的环，在坐标 $0,X+1,X+Z+2$ 处各有一个棋子，每次可以选取一个棋子往钦定的正方向移动一步，满足恰好移动 $n$ 次且 **任意时刻棋子不重合** 的方案数。
记录当前三个棋子的坐标进行 dp 即可做到 $\mathcal{O}(nm^3)$，但这也太不牛了。
### Part 2
发现我们并没有用到答案模 $2$ 这个性质。
一个非常难受的部分是限制 **移动过程中棋子不能重合**，这导致我们要记录棋子坐标。
但是如果真的存在某个时刻 $i$ 两个棋子重合了，不妨设接下来两个棋子的移动路径分别为 $A,B$，**则 $\operatorname{swap}(A,B)$ 后仍然是一种合法的方案**！且除非 $A=B=\empty$，否则这是一种新的方案。也就是除去 $A=B=\empty$ 外，**剩余方案总数恰为偶数，不对答案产生贡献**！
再来考虑 $A=B=\empty$，则在最终时刻这两个棋子仍是重合的，所以若考虑模 $2$ 意义下的答案仅仅只需要拿总方案数减去 **最终** 某两颗棋子重合的方案数！
当然容易注意到我三个棋子全部重合的情况杯多记了两次，所以要减掉，但事实既然是 **两倍** 也就不对答案产生贡献了。
且总方案数为 $3^n$，这是个奇数，那答案也就是三种情况（一二棋子重合，一三棋子重合，二三棋子重合）的奇偶性异或和再异或上 $1$。
### Part 3
下面以计算一二两棋子重合的方案数为例。
经典的，判断重合我们也就不关心其具体坐标，仅仅只关心 **坐标差值**。
每次挪动棋子，坐标差值 **要么加一，要么减一，要么不变**，这在草稿纸上画一下是显然的。
则将其刻画为生成函数的形式：
$$[x^{X+1}]\left((x^{-1}+1+x)^n\bmod{x^m-1}\right)$$
意义显然。其中 $\bmod\ {x^m-1}$ 刻画为长度为 $m$ 的多项式做循环卷积。$m$ 即为环长也就是 $X+Y+Z+3$。
比较经典的，我们有：（用到这个 trick 的还有 [ARC184E](https://www.luogu.com.cn/article/gfbxt484)）
$$(x^{-1}+1+x)^{2^k}\equiv x^{-2^k}+1+x^{2^k}\pmod{2}$$
还是写一下证明：
$$
\begin{aligned}
(x^{-1}+1+x)^{2^k} & \equiv\sum\limits_{a+b+c=2^k}\binom{2^k}{a,b,c}x^{-a}x^{c}\\
& \equiv\sum\limits_{0\le a+b\le 2^k} \binom{2^k}{a}\binom{2^k-a}{b}x^{-a}x^{2^k-a-b}\\
& \equiv\sum\limits_{0\le a+b\le 2^k} \left[a\subseteq 2^k\right]\left[b
\in 2^k-a\right]x^{-a}x^{2^k-a-b}\\
\end{aligned}
$$
其中最后一步是 Lucas 定理推论。$a\subseteq 2^k$ 仅在 $a=0$ 或 $a=2^k$ 时成立，这样子 $(a,b)$ 有值的取值就只有 $\mathcal{O}(1)$ 种了，进一步分讨即可得到，这里不再赘述。
则将 $n$ 写作 $n=\sum\limits_{i=1}^k 2^{p_i}$ 也就得到：
$$\text{answer}=[x^{X+1}]\left(\prod_{i=1}^k \left(x^{-2^{p_i}}+1+x^{2^{p_i}}\right)\bmod{x^m-1}\right)$$
我们有 $k\le \log{n}$，且做单次循环卷积暴力就是 $\mathcal{O}(m)$ 的，我们也就获得了一个 $\mathcal{O}(m\log{n})$ 的做法。
### Part 4
Part 3 得到的做法当 $m$ 较小时已经可以接受，但是 $m$ 较大时仍然无法通过。
考虑略去 $\bmod\ {x^m-1}$ 循环卷积的限制，我们则得到：
$$\text{answer}=\sum\limits_{r\equiv X+1\pmod{m}}[x^r]\left(\prod_{i=1}^k \left(x^{-2^{p_i}}+1+x^{2^{p_i}}\right)\right)$$
将 $r$ 写作 $r=qm+(X+1)$ 的形式，注意到 $r\le n\Rightarrow-\left\lfloor\cfrac{n}{m}\right\rfloor\le q\le \left\lfloor\cfrac{n}{m}\right\rfloor$。**这样子 $r$ 只有 $\mathcal{O}\left(\cfrac{n}{m}\right)$ 种取值**，若我们能快速求解单个 $x^r$ 次项的系数，那复杂度也是可以接受的。
为了消去负指数的影响，我们将多项式乘上 $x^n$：
$$\text{answer}=\sum\limits_{r\equiv (X+1)+n\pmod{m}}[x^r]\left(\prod_{i=1}^k \left(1+x^{2^{p_i}}+x^{2^{p_i+1}}\right)\right)$$
若我们将连乘式暴力展开，实际上就是有 $k$ 个三元组 $\left(0,2^{p_i},2^{p_i+1}\right)$，每个三元组中恰选一个数，求和为 $r$ 的方案数。
进一步也将 $r$ 排成二进制，就变成了每个三元组 **可以选择不变，将第 $p_i$ 位加一，或将第 $p_i+1$ 位加一**。
记录 dp 状态为 $f_{i,0/1}$ 表示考虑 $i\sim \log{n}$ 位，其中第 $i+1\sim \log{n}$ 位已经完全符合要求，和 **是否需要在第 $i-1$ 位进位补充** 的方案数。
转移可能看代码会很清晰？
答案即为 $f_{0,0}$。
这样子我们做到了 $\mathcal{O}(\log{n})$ 复杂度算一个 $x^r$ 项系数，复杂度即为 $\mathcal{O}\left(\cfrac{n}{m}\log{n}\right)$。
### Part 5
经典的，我们阈值分治，钦定 $m\le B$ 使用 Part 3，$m>B$ 使用 Part 4。视 $n,m$ 同级，取 $B=\sqrt{n}$ 即可获得 $\mathcal{O}(\sqrt{n}\log{n})$ 复杂度的做法。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
const int B=1e5,N=B+5,M=35;
int f[N],tmp[N],g[M][2];
int calc1(int x,int m,int n) {
rep(i,0,m-1)
f[i]=0;
f[0]=1;
int k=lg(n);
rep(i,0,k) {
if((n>>i)&1) {
rep(j,0,m-1) {
tmp[j]=f[j];
f[j]=0;
}
rep(j,0,m-1) {
f[((j-(1ll<<i))%m+m)%m]^=tmp[j];
f[j]^=tmp[j];
f[(j+(1ll<<i))%m]^=tmp[j];
}
}
}
return f[x%m];
}
int calc2(int x,int m,int n) {
int k=lg(x);
rep(i,0,k+1)
g[i][0]=g[i][1]=0;
g[k+1][0]=1;
per(i,k,0) {
if((n>>i)&1) {
if((x>>i)&1) {
g[i][0]^=g[i+1][0]; // choose 1
g[i][1]^=g[i+1][0]; // choose 0
g[i][1]^=g[i+1][1]; // choose 2
} else {
g[i][0]^=g[i+1][0]; // choose 0
g[i][0]^=g[i+1][1]; // choose 2
g[i][1]^=g[i+1][1]; // choose 1
}
} else
g[i][(x>>i)&1]=g[i+1][0];
}
return g[0][0];
}
int calc(int x,int m,int n) {
if(m<=B)
return calc1(x,m,n);
int t=(x+n)%m,res=0;
rep(i,0,((n<<1)-t)/m)
res^=calc2(t+i*m,m,n);
return res;
}
void solve() {
int n,x,y,z;
scanf("%lld%lld%lld%lld",&n,&x,&y,&z);
int t=x+y+z+3;
printf("%lld\n",1^calc(x+1,t,n)^calc(y+1,t,n)^calc(z+1,t,n));
}
bool M2;
// g++ ARC147F.cpp -std=c++14 -Wall -O2 -o ARC147F
signed main() {
// file_IO();
int testcase=1;
scanf("%lld",&testcase);
while(testcase--)
solve();
debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
return 0;
}
```