[ABC317F] Nim
这个问题可以通过数位动态规划(DP)来解决。
我们考虑以下的数位DP来确定从二进制表示的最低位开始的下一位:
\(\mathrm{DP}[n][f_1][f_2][f_3][r_1][r_2][r_3]=\) 满足以下条件的整数组 \((x_1,x_2,x_3)\) 的个数:
- 对于所有 \(i\),\(0 \leq x_i < 2^n\)
- \(x_1\oplus x_2\oplus x_3=0\)
- 对于每个 \(i\),"\(x_i\) 在 \(N\&(2^n-1)\) 以下"的真假为 \(f_i\)
- 对于每个 \(i\),\(x_i\) 除以 \(A_i\) 的余数为 \(r_i\)
这里,\(\&\) 表示按位与运算。也就是说,\(N\&(2^n-1)\) 表示 \(N\) 的二进制表示的最低 \(n\) 位的值。
通过尝试每个 \(x_i\) 在二进制表示中从最低位开始的 \(n\) 位的值(共 \(2^3\) 种可能),我们可以从 \(\mathrm{DP}[n][*][*][*][*][*][*]\) 推导出 \(\mathrm{DP}[n+1][*][*][*][*][*][*]\)。
根据给定的约束条件 \(N < 2^{60}\),\(\mathrm{DP}[60][\mathrm{True}][\mathrm{True}][\mathrm{True}][0][0][0]\) 表示满足以下条件的整数组 \((x_1,x_2,x_3)\) 的个数:
- 对于所有 \(i\),\(0 \leq x_i \leq N\)
- \(x_1\oplus x_2\oplus x_3=0\)
- 对于每个 \(i\),\(x_i\) 是 \(A_i\) 的倍数
所求答案是从第一个条件为 "对于所有 \(i\),\(1 \leq x_i \leq N\)" 的情况中减去得到的结果,即:
- 对于某个 \(i\),\(x_i=0\)
- \(x_1\oplus x_2\oplus x_3=0\)
- 对于每个 \(i\),\(x_i\) 是 \(A_i\) 的倍数
这个可以很容易地计算出来。(分别令 \(x_1,x_2,x_3=0\),计算剩余二者的 \(\text{lcm}\),最后算出来,注意还有三者均为 \(0\))。
计算复杂度为 \(O(\log N \prod A_i)\)。