题目
有一个长度为 \(n\) 的序列 \(a\)。
选定 \(n,k\) ，并让 \(a_i\) 在 \([0,2^k)\) 的范围内均匀随机生成。
求生成出 \(a\) 能够被划分成两段使两段的或和相同的概率。
\(n\le 10^5,k \le 10^9\)
-
不会推式子，哈哈（悲）。
然而很幸运的是这题不一定需要推式子。
观察到原题可以分成 \(k\) 位来考虑。
设第 \(i\) 位在序列上第一次和最后一次出现的位置分别为 \(l_i,r_i\)。
同时设划分线在第 \(t\) 个位置之后。
显然有 \(t \in [L,R]= \bigcap_{i=0}^{k-1}[l_i,r_i)\)。
那么钦定 \(t\) 在 \(L\) 上，这样不会算重。
那么现在一种思路是对于每个 \(t\) 贡献分别为多少。
然后似乎可以推出一个计算复杂度为 \(O(nk)\) 甚至 \(O(nk^2)\) 的式子，然而不会化。
考虑直接从组合意义下手上下手。
我们只考虑当前位置 \(t\)。
设 \(f_j\) 表示考虑前 \(j-1\) 位划分线两边合法且在当前情况下 \(t\) 不为 \(L\)。
同理，设 \(g_j\) 表示考虑前 \(j-1\) 位划分线两边合法且在当前情况下 \(t\) 已经为 \(L\)。
可以得到转移式：
\[\begin{aligned}
&\begin{cases}
f_0 = 1 \\
g_0 = 0 \\
\end{cases} \\
&\begin{cases}
f_j = ((2^t-2)(2^{n-t} - 1) + 1)f_{j-1} \\
g_j = (2^{n-t}-1)f_{j-1} + ((2^t - 1)(2^{n-t}-1)+1)g_{j-1} \\
\end{cases}
\end{aligned}
\]
\((2^u-1)\) 之类的常数大家应该都知道为什么，而 \((2^t-2)\) 是因为在不算全部不选的情况下也不算只选第 \(t\) 位置上的数。而 \(((2^t - u)(2^{n-t}-1)+1)\) 之类的常数里面的 \(+1\) 是指当前位在所有位置上都不选的情况。
然后划分线为 \(t\) 的贡献就是 \(g_k\)，直接矩阵快速幂计算即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n, k, Ans = 1;
struct matrix {
int a[2][2];
void init (int p){
for (int i = 0;i < 2;++ i)
for (int j = 0;j < 2;++ j)
a[i][j] = (i == j) ? p : 0;
}
matrix (){
init (0);
}
matrix operator * (const matrix b) const {
matrix res;
for (int i = 0;i < 2;++ i)
for (int j = 0;j < 2;++ j)
res.a[i][j] = (a[i][0] * b.a[0][j] % mod + a[i][1] * b.a[1][j] % mod) % mod;
return res;
}
} A, B;
int pow_n (int a, int p){
int res = 1;
while (p > 0){
if (p & 1)
res = res * a % mod;
p >>= 1;
a = a * a % mod;
}
return res;
}
matrix pow_m (matrix a, int p){
matrix res;
res.init (1);
while (p > 0){
if (p & 1)
res = res * a;
p >>= 1;
a = a * a;
}
return res;
}
signed main (){
scanf ("%lld%lld", &n, &k);
for (int i = 1;i < n;++ i){
A.init (0);
A.a[0][0] = 1;
A.a[0][1] = 0;
B.a[0][0] = ((pow_n (2, i) - 2) * (pow_n (2, n - i) - 1) % mod + 1 + mod) % mod;
B.a[0][1] = (pow_n (2, n - i) - 1 + mod) % mod;
B.a[1][1] = ((pow_n (2, i) - 1) * (pow_n (2, n - i) - 1) % mod + 1) % mod;
A = A * pow_m (B, k);
Ans = (Ans + A.a[0][1]) % mod;
}
Ans = Ans * pow_n (pow_n (pow_n (2, k), n), mod - 2) % mod;
printf ("%lld\n", Ans);
return 0;
}