ACL Beginner Contest F(Heights and Pairs)题解——分治NTT
Description
一个序列有 2 n 2n 2n个数，现在你要在这个序列中配得 n n n个无序数对，使得每一对的两个数不同且每个数都在恰好 1 1 1个对中。
请求出合法配对的方案数。注意 ( 1 , 3 ) ( 2 , 4 ) (1,3)(2,4) (1,3)(2,4)与 ( 2 , 4 ) ( 1 , 3 ) (2,4)(1,3) (2,4)(1,3)这两种配对方式是等价的。
请将答案对 998244353 998244353 998244353取模。
n ≤ 50000 , a i ≤ 1 0 5 n≤50000,a_i≤10^5 n≤50000,ai≤105
Solution
考虑 d p dp dp。
如果按照整个序列去进行 d p dp dp的话很难设计出合理的状态，所以考虑开桶 d p dp dp，并令 v i v_i vi表示第 i i i个桶的大小。根据题意，每一个桶中的数不能进行匹配，不难得到状态设计与状态转移：
d p i , j dp_{i,j} dpi,j表示看到第 i i i个桶(即已经处理了 1 1 1至 i i i号桶)，还剩 j j j个人未匹配的方案数。
状态转移如下:
d p i , j = ∑ k = 0 v i C v i k A j − ( v i − k ) k k d p i − 1 , j − ( v i − k ) k dp_{i,j}=\sum_{k=0}^{v_i}\ C_{v_i}^k\ A_{j-(v_i-k) k}^k\ dp_{i-1,j-(v_i-k) k} dpi,j=∑k=0vi Cvik Aj−(vi−k) kk dpi−1,j−(vi−k) k
解释一下这个状态转移。 k k k枚举的是在 i i i这个桶内与前面匹配掉的数的数量。 C v i k C_{v_i}^k Cvik表示在第 i i i个桶中选择 k k k个与前面进行匹配。由于看到第 i i i个桶还剩 j j j个数未匹配，第 i i i个桶本身对“未匹配的量”的贡献是 v i − k v_i-k vi−k，并且前面还要多留 k k k个数与第 i i i个桶选中的数进行匹配，所以之前未匹配的数的数量应该是 j − ( v i − k ) k j-(v_i-k) k j−(vi−k) k。在这个里面选 k k k个数与第 i i i个桶中选定的 k k k进行匹配的方案数为 A j − ( v i − k ) k k A_{j-(v_i-k) k}^k Aj−(vi−k) kk。
每次暴力转移的时间复杂度是 O ( n 3 ) O(n^3) O(n3)的，严重超时。我们先尝试将它优化到 O ( n 2 ) O(n^2) O(n2)或类 O ( n 2 ) O(n^2) O(n2)。
我们拆开状态转移式中的括号并观察：
d p i , j = ∑ k = 0 v i C v i k A j − ( v i − k ) k d p i − 1 , j − ( v i − k ) k dp_{i,j}=\sum_{k=0}^{v_i}\ C_{v_i}^k\ A_{j-(v_i-k) k}\ dp_{i-1,j-(v_i-k) k} dpi,j=∑k=0vi Cvik Aj−(vi−k) k dpi−1,j−(vi−k) k
d p i , j = ∑ k = 0 v i C v i k A j − v i 2 k d p i − 1 , j − v i 2 k dp_{i,j}=\sum_{k=0}^{v_i}\ C_{v_i}^k\ A_{j-v_i 2k}\ dp_{i-1,j-v_i 2k} dpi,j=∑k=0vi Cvik Aj−vi 2k dpi−1,j−vi 2k
考虑将 d p i − 1 dp_{i-1} dpi−1翻转，就得到了一个卷积的形式。每次跑一遍 N T T NTT NTT，时间复杂度优化到 O ( n 2 log n ) O(n^2 \log n) O(n2logn)。
但是我们依然不满意。不难发现这个状态转移可以用cdq分治来优化，即分治NTT。每次我们递归左半边，跑一遍NTT处理左半边对右半边的贡献再往后边递归。由于递归的深度最大是 log n \log n logn的，所以卷积的次数为 n log n n \log n nlogn次，总时间复杂度为 O ( n log 2 n ) O(n \log^2 n) O(nlog2n)。
NTT txdy!
Summary
在本题中，我们巧妙设计了 d p dp dp状态，发现翻转后是一个卷积的形式，从而采用分治NTT将时间复杂度优化到了 O ( n 2 log n ) O(n^2 \log n) O(n2logn)。
可以说这是一道比较套路的题，唯一较为灵活的就是 d p dp dp的状态设计以及状态转移。分治NTT出来得比较自然，可惜蒟蒻(我)在想这题的时候并不会分治NTT，是在看了别人的题解之后才悟懂。
感觉这题放在ABC的F题是不是太过分了啊？？？