ARC147F

Description

求长度为

n

且字符集为

\{\tt A,\tt B,\tt C\}

，满足如下条件的的字符串

S

数量：

设 $C_{i,\tt A},C_{i,\tt B},C_{i,\tt C}$ $C_{i, A}, C_{i, B}, C_{i, C}$ 分别为字符串 $S_{[1,i]}$ $S_{[1, i]}$ 中 $\tt A,\tt B,\tt C$ $A, B, C$ 的出现次数，则对于任意 $1\le i\le n$ $1 \leq i \leq n$ 有：
- $C_{i,\tt A}-C_{i,\tt B}\le X$ 。
- $C_{i,\tt B}-C_{i,\tt C}\le Y$ 。
- $C_{i,\tt C}-C_{i,\tt A}\le Z$ 。

答案对 $\mathbf{2}$ 取模。

1\le n,X,Y,Z\le 10^9

。

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）

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

文章操作