03.16 蚂蚁 && 阿里云笔试

阿里云 好难好难 T1被卡爆 只能做T2+T3

阿里云

T1

给定两个整数 n 和 k，考虑长为 n 的序列 (a[1], a[2], …, a[n])，其中每个 a[i] 都满足 0 ≤ a[i] < 2^k。要求计算满足下式的序列个数：

a[1] ⊕ a[2] ⊕ … ⊕ a[n] ≤ a[1] & a[2] & … & a[n]

并将答案对 1e9+7 取模。

其中

• ⊕ 表示按位异或 (XOR)

• & 表示按位与 (AND)

dp，分奇数/偶数考虑，偶数最高位全1后面任选，否则就需要考虑后续情况

**动态规划**:

-使用动态规划逐位处理，维护两种状态：

- `met`：已经确定异或结果小于按位与结果。

- `not_met`：尚未确定，需要继续比较后续位。

-对于每个位，计算其可能的转移情况，并更新状态。

代码大概这样（？

```CPP

long long pow2n = pow_mod(2, n, MOD);

long long pow2_half = pow_mod(2, n-1, MOD);

long long met = 0, not_met = 1;

for (int i =0; i < k; ++i) {

// n个数字0/1选法

long long new_met = (met * pow2n) % MOD;

long long new_not_met;

if (n %2 ==0) {

new_met = (new_met + not_met) % MOD;

// 去掉全1的情况 还要比较后面的情况 (2^{n-1}-1) 种可能

long long s = (pow2_half -1 + MOD) % MOD;

new_not_met = (not_met * s) % MOD;

} else {

// 11/111100/1111000... 必须要有偶数个1 + 全1的情况

long long s = (1 + pow2_half) % MOD;

new_not_met = (not_met * s) % MOD;

}

met = new_met;

not_met = new_not_met;

}

```

#笔试#

T2

Codeforces Competitive Fishing 变形

算式首先去掉op(j)*a[j]这个东西（定制）

考虑分在第j段的增益，suf[i]表示从i到n的后缀1/-1和（01串 1看成+1，0看成-1）

1*(suf[0]-suf[l1]) + 2*(suf[l1] - suf[l2]) + ... + k * (suf[lk-1] - suf[n] = 0)

写出来移项就会变成后缀和取前k-1个最大的

排序 or 堆 都可以

T3

乍看很吓人实际上就是两数之和变形，

这里就是暴力枚举$2^i$ 的步长对应前缀和是否存在（i反正<63)

所以是O(nlogn*logU)可以卡过去

蚂蚁笔试就正常许多

T1

无限重复字符串 第i行打印i个字符

求出最终打印p行的每个行头字符

- 字符串模拟 + 注意取个模

T2

不能出现110模式的最大权重和

- 状态机dp + 选或不选

`dp[i][state]`

考虑上次后缀选的2个字符情况，00/01/10/11就是需要11后不能接0即可。

代码很短，注意爆int

T3

L型矩阵 1出现在最外侧的情况

- 数学题 + 递推

考虑特殊点：1出现在边上，和4个角的情况

- 角上的1在下一阶矩阵继续成为角情况是一一对应的

- 边上的1在下一矩阵中有2种可能， 也有来自于上一层角上的2种可能

初始`f[1]=1, g[1]=0 f[2]=4, g[2]=0`

- `f[i+1] = f[i]`

- `g[i+1] = g[i]*2ll + f[i]*2`

因为n很小只有`1e5`所以`O(n)`遍历即可，如果n是`1e9`考虑快速幂求解

#笔试#

#牛客AI配图神器#