LOJ3058 [HNOI2019]白兔之舞

过程比较繁琐,知识比较综合。

题意:在 L+1n 列的图形上从 (0,x) 随机游走,要求只能向下走,从 v1 列走到 v2 列的方案数为 Wv1,v2(与行无关),只能在 y 列停止。给定 k,求所有 t[0,k1],求停留的行的编号满足 modk=t 的所有方案和,答案对 p 取模。满足 k216L108108<p<230n3k|p1p 为质数。

仔细观察发现如果我们确定步数 k,行和列的答案是无关的,只需要最后乘起来即可。对于行来说,我们假设多给一步,强制走到 L+1 的位置,于是插板法容易得到方案数为 (Lk)。对于列来说,这就是一个显然的矩阵乘法,为 Wk[x][y]

于是可以得到:

anst=i=0L[imodk=t]Wi[x][y](Li)

然后看到 [imodk=t],果断单位根反演,于是一波变换:

anst=i=0L[imodk=t]Wi[x][y](Li)=1ki=0LWi[x][y](Li)j=0k1ωkijtj=1kj=0k1ωktji=0LWi[x][y]ωkij(Li)=1kj=0k1ωktj(ωkjW+I)L[x][y]

最后一步我们在 单位根反演 的 T2 中已经见过矩阵合并二项式定理了,这里不再赘述。注意这里单位根需要我们先求出原根计算。

假设后面只关于 j 的一坨记作 f(j),其为 j=0k1ωktj(ωkjW+I)L[x][y]。单个 f(j) 容易在 logL 的时间完成。

于是我们得到:

k×anst=j=0k1ωktjf(j)

看样子这是一个卷积,但是指数上有乘积,不好拆开。

考虑如下两个变换:

(x+y)2x2y2=2xy(x+y2)(x2)(y2)=xy

两个式子展开一下即可证明。我们惊喜的发现,这个恰好把 xy 化为了 (x+y),这样看样子就可以卷积了!

套用第一个式子:

k×anst=ωkt22j=0k1f(j)ωkj22ωk(j+t)22

但是除以 2 不好处理,因为我们可能没法开根。

考虑套用第二个式子:

k×anst=j=0k1ωktjf(j)=j=0k1ωk(t2)+(j2)(t+j2)f(j)=ωk(t2)j=0k1f(j)ωk(j2)ωk(j+t2)

显然这是一个差卷积,直接做即可,时间复杂度 O(klogk),可以通过。

另外,这后半部分拆开指数上的乘积其实就是一个叫 BlueStein 的算法。容易发现这个算法其实解决了任意长度的 FFT,因为 FFT 和这个算法都是计算 n 个单位根位置的点值的,只不过 FFT 的 n 是 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