过程比较繁琐,知识比较综合。
题意:在 行 列的图形上从 随机游走,要求只能向下走,从 列走到 列的方案数为 (与行无关),只能在 列停止。给定 ,求所有 ,求停留的行的编号满足 的所有方案和,答案对 取模。满足 ,,,,, 为质数。
仔细观察发现如果我们确定步数 ,行和列的答案是无关的,只需要最后乘起来即可。对于行来说,我们假设多给一步,强制走到 的位置,于是插板法容易得到方案数为 。对于列来说,这就是一个显然的矩阵乘法,为 。
于是可以得到:
然后看到 ,果断单位根反演,于是一波变换:
最后一步我们在 单位根反演 的 T2 中已经见过矩阵合并二项式定理了,这里不再赘述。注意这里单位根需要我们先求出原根计算。
假设后面只关于 的一坨记作 ,其为 。单个 容易在 的时间完成。
于是我们得到:
看样子这是一个卷积,但是指数上有乘积,不好拆开。
考虑如下两个变换:
两个式子展开一下即可证明。我们惊喜的发现,这个恰好把 化为了 ,这样看样子就可以卷积了!
套用第一个式子:
但是除以 2 不好处理,因为我们可能没法开根。
考虑套用第二个式子:
显然这是一个差卷积,直接做即可,时间复杂度 ,可以通过。
另外,这后半部分拆开指数上的乘积其实就是一个叫 BlueStein 的算法。容易发现这个算法其实解决了任意长度的 FFT,因为 FFT 和这个算法都是计算 个单位根位置的点值的,只不过 FFT 的 是 2 的次幂。更详细的信息看 这篇 Blog。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| int main() { Matrix a; int k, L, x, y, G; std::cin >> n >> k >> L >> x >> y >> Mod, -- x, -- y; for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) std::cin >> a[i][j]; w = qpow(G = findrt(), (Mod - 1) / k); poly f(k); for (int l = 0; l < k; ++ l) { static Matrix tmp; int cur = qpow(w, l); for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) tmp[i][j] = ((LL) a[i][j] * cur + (i == j)) % Mod; f[l] = qpow(tmp, L)[x][y]; } for (int i = 0; i < k; ++ i) f[i] = (LL) f[i] * qpow(w, (i - 1LL) * i / 2 % (Mod - 1)) % Mod; std::reverse(f.begin(), f.end()); poly g(2 * k); for (int i = 0; i < 2 * k; ++ i) g[i] = qpow(w, (Mod - 1 - i * (i - 1LL) / 2 % (Mod - 1)) % (Mod - 1)); f = f * g, f = std::vector<int>(f.data() + k - 1, f.data() + 2 * k - 1); for (int i = 0; i < k; ++ i) f[i] = (LL) f[i] * qpow(w, (i - 1LL) * i / 2 % (Mod - 1)) % Mod * qpow(k) % Mod; for (int &x : f) printf("%d\n", x); return 0; }
|
Related Issues not found
Please contact @mydcwfy to initialize the comment