题目来源于CF2072FProblem - F - Codeforces ↗ 我们需要生成一个魔法三角形的第 nn 行。这个三角形的定义如下：

第 i行有 i个整数。
第一行只有一个整数 k。
对于第 i 行的第 j个元素 $T_i,T_j$ $T_{i}, T_{j}$ 其值由以下规则决定：
- 如果 $1<j<i$ ，则 $T_{i,j}=T_{i-1,j-1}$ ⊕ $T_{i-1,j}$ （即上一行的第 j−1 和第 j 个元素的异或结果）。
- 如果 j=1，则 $T_{i,j}=T_{i-1,j}$ （即上一行的第一个元素）。
- 如果 j=i，则 $T_{i,j}=T_{i,j-1}$ （即上一行的最后一个元素）。

当k = 3时：
        3 
       3 3 
      3 0 3 
     3 3 3 3 
     
    3 0 0 0 3 
   3 3 0 0 3 3 
  3 0 3 0 3 0 3 
 3 3 3 3 3 3 3 3 
 
3 0 0 0 0 0 0 0 3

plaintext

方法一：递归#

我们发现三角形在 $2^k$ 行都全为k，并且是由边长为2的全为k的三角形以及对应边长的0的三角形组合而成。子结构相似，可以递归。

void solve(){
	int n,k;
	cin>>n>>k;
	auto go = [&](this auto &&self,unsigned t)->void{
		if(t==1) cout<<k<<" ";
		else if(t==2) cout<<k<<" "<<k<<" ";
		else
		{
			int w = bit_width(t);
			if(t == (1<<(w-1)))
			{
				for(int i =1;i<=t;i++)
					cout<<k<<" ";
			}
			else
			{
				unsigned x = t - (1<<(w-1));
				self(x);
				for(int i = 1;i<=t-2*x;i++)
					cout<<0<<" ";
				self(x);
			}
		}
	};
	go(n);
	cout<<endl;
}

cpp

方法二：二项式系数的模 2 形式#

异或操作的性质使得魔法三角形的每一行实际上是一个 二项式系数的模 2 形式。
具体来说，第 n 行的第 j 个元素的值取决于 $\tbinom{n-1}{j-1}mod2$ 二项式系数 $\tbinom{n-1}{j-1}mod2$ 可以通过位运算来计算当且仅当 $(n-1)\&(j-1)==(j-1)$ 时成立

$\tbinom{n}{k}$ 逐位比较 n 和 k 的二进制表示：

如果 k的某一位为 1，而 n的对应位为 0，则模2为0
否则，模2为1

//jiangly
void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cout << (((n - 1) & i) == i ? k : 0) << " \n"[i == n - 1];
    }
}

cpp

魔法三角形以及二项式系数的模2形式

方法一：递归#

方法二：二项式系数的模 2 形式#