题解：CF2072F Goodbye, Banker Life

前言：怎么说呢，这道题说简单也不简单，说难也不难，简单到找规律也可以写出来，难到不想找规律几乎想不出来……

题目简化：没什么好简化的，题目已经说的很清楚了，就是求一个表的第 $n$ 行的数字，这个表满足下列条件：

• 第 $i$ 行包含 $i$ 个整数。

• 第一行唯一的整数是 $k$。

• 设第 $i$ 行第 $j$ 列的数为 $T_{i,j}$，则：

$$T_{i,j}=\{\begin{array}{ll}{T}_{i-1,j-1}\oplus T_{i-1,j}& 1<j<i\\ T_{i-1,j}& j=1\\ T_{i-1,j-1}& j=i\end{array}$$

突然发现讲着讲着好像复述了一遍题目。

看到这道题，我首先得想法就是找规律。请看这张图：

这里是我列了 $12$ 行后的图，不难发现：每一行都是对称的，但规律并不是很明显，你们也可以尝试着自己多列几个看看能不能找出规律。

因此，我们就不得不采取第二种方法：算正解。我是这样想的。

因为题目中有异或，而跟异或相关的有一个东西：加法。只不过它是没有进位的加法。这里又有个图表，所以我立马想到了杨辉三角。所以我先对这个图的每一个点都除以一个 $k$，这样就成了一个 01 序列，更方便我们理解后面的东西。

然后我们就可以把杨辉三角带进去了，杨辉三角满足 $f_{i,j}=f_{i-1,j-1}+f_{i-1,j}$，跟题目中的一个条件很像，正好也能说明这个思路大概率是对的。但整个图表只有 0 和 1，没有其他的数，这咋办呢？

这也很简单：对杨辉三角的每个数 $\mathrm{mod}2$ 就行了。事实证明这样做也能得到原来的 01 序列。

我们又知道杨辉三角的每一项为 $C_{j-1}^{i-1}$，带入可得第 $i$ 行第 $j$ 列的数是：

$$f_{i,j}=C_{j-1}^{i-1}\mathrm{mod}2$$

又根据 Lucas 定理（$C_n^m\mathrm{mod}p=C_{\lfloor \frac{n}{p}\rfloor }^{\lfloor \frac{m}{p}\rfloor }\times C_{n\mathrm{mod}p}^{m\mathrm{mod}p}\mathrm{mod}p$）可知：

$$f_{i,j}=C_{\frac{j-1}{2}}^{\frac{i-1}{2}}\times C_{(j-1)\mathrm{mod}2}^{(i-1)\mathrm{mod}2}\mathrm{mod}2$$

因为 $1$ 的情况不好算，所以我们来看 $0$ 的情况。

如果上面那个式子是 $0$，说明两项之积为偶数，但当我们把前面不断拆分之后就会发现只有当 $C_{(j-1)\mathrm{mod}2}^{(i-1)\mathrm{mod}2}$ 为偶数时才成立，而 $C_{(j-1)\mathrm{mod}2}^{(i-1)\mathrm{mod}2}$ 为偶数的情况只有一种：$C_{(j-1)\mathrm{mod}2}^{(i-1)\mathrm{mod}2}=0$。由此可知：当 $(i-1)\mathrm{mod}2=0$ 且 $(j-1)\mathrm{mod}2=1$ 时，上述条件才成立（因为没有 $C_0^0$ 这个东西），这说明 $i-1$ 和 $j-1$ 在二进制内必然有一位不等，与运算一下就可知，其中 $\&$ 表示与运算：

$$(i-1)\&(j-1)\ne j-1$$

那么把上述条件反过来就是等于 $1$ 的情况。

最后把先开始除以的 $k$ 乘回去就可以得到：

$$f_{i,j}=k\times [(i-1)\&(j-1)=j-1]$$

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k;
signed main()
{cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++){cout<<(((i-1)&(n-1))==i-1?k:0)<<" ";//带入公式}cout<<endl;}return 0;
}