总结 腊月初二。今天是模拟赛,还行,很有趣。D2 改完了,还有一道题。简单讲一讲,今天发挥还是没有完全发挥感觉,有一点兴致低落。D2T1 都想了好久,后面就没有太大动力了。需要改正。
题解 有两道题知道出处,其他两道不知道。
原题:IOI 2016 Day2 Paint By Numbers 。
简要题意:给定一个长度小于等于 的序列和一个不完整的 01 串,要求这个 01 串把黑色连通块长度按顺序搞下来之后和序列一样,让你求对于所有可能填法,如果一个位置固定 0 或 1 就输出这个数,不然输出问号。这个就正着反着 dp 一下然后验证一下就行。
有空间内 个点,你要从 到 ,然后每个点做匀速直线运动或静止,每一维初始坐标绝对值小于等于 且是整数。 ,在每个点最多停留 秒,每次可以在一瞬间在从当前点跳到另外一个点,跳不一定是整数秒。然后求跳的路径中最长距离的最小值。
考虑二分,然后会发现两个点如果会出现边,就一定是一个区间。然后维护这 个时间各个点是否可以到达。如果中间到达了 ,那么就可以。否则就不行。所以维护每条边加和删除的时间,然后所有混在一起排序。对于 S 的限制,我们容易发现如果一个时间一个点有出度,那么可以来回横跳,就没有关系。只有单独的时候就有。所以加边的时候维护一下两个点是否存在就行。然后如果加边是一个点有另一个点没有,就 dfs/bfs 没有的点,这个时间来转移还不能到的点,访问过的边就直接删掉。然后删除边就减一下度数,把边删掉(如果还没删)。如果度数为 0 了,就记录一下现在的时间就行。
P.S. 不用删边那些的也能过,暴力枚举就行,如果想更好可以使用 bitset,用 vector 的话不会。
找不到原题。
就是一个树,每个点一个权值,然后求每个子树,A 先选择其中一个点的权值,B 后选择另外一个点的权值,然后 A 想使得异或尽量大,B 想使得异或尽量小,求这个值。就是用 Trie,然后用类似线段树合并的方法就行。
这道原题。但是数据范围变成了 。
为什么会有人模拟赛搬 AGC F 啊?
洛谷题解都看得不是很懂,nflsoj 上面的倒是很有趣。
知识点:元素合并有两种表示方式,一种是 个点的二叉树,一种是就是普通的数,爹爹干掉合并上儿子,儿子的排列就是合并的顺序。
终于会 做法了!
这里准备直接把他的题解 copy 过来,主要是他讲得太好了,令人动容,而且比我讲的好,未来还可以再看看,再想想。绝对不是因为我懒。
每次做这种 atc 风格 DP 都是生不如死……
先扯一些关系不大的东西。
我们知道 个元素合并 次可以用一棵 个点的二叉树表示。每次合并都新建节点,并连向两个集合的树的根,得到一棵新树。这样可以描述每次合并的两个集合的无序对的集合,但并不能知道合并的顺序(也不会有题目需要知道顺序),但起码需要符合这棵树的拓扑序。如果 A 合并到 B、B 合并到 A 不同(可以理解为 PK 的胜负,负者淘汰),那么此时这种方法并不能记录每次的输赢,但只需要把胜者放在左儿子、负者放在右儿子即可。
但还有另一种我以前不知道的描述合并关系的方法。这种方法重在描述每次合并的胜负,每次合并设 A 胜 B 负,则令 B 目前的胜者直接指向 A 目前的胜者。这样也可以得到一棵(内向)树,只不过恰有 个节点,且是多叉树(相当于把二叉树的左儿子缩上去)。但普通情况并不能描述每次合并的两个集合的无序对的集合,然而依然可以稍作改进做到。对于某个节点 ,记其儿子序列为 ,则必然恰好存在一个排列 ,使得 参与的合并是与 合并的,那就将儿子序列按照这个排列排序即可。这种方法依然不能知道合并顺序,但可以肯定合并是按照树的拓扑序进行的。所以这和二叉树方法是等价的。
开始讲这个题。可以认为一开始是 个向量 ,使得 。每次 PK 是合并为 或 。注意到,这里涉及胜负,而多叉树描述法擅长描述这个。我之前只知道二叉树描述法,推了半天毫无头绪/yun
考虑其多叉树。每次胜者的集合里所有 对最终向量的第 分量贡献了 的系数,负者贡献 。设第 分量为 ,尝试将 在树上表示出来。 显然就是 的深度。而 比较复杂,好在我们只关心其奇偶性。
在 往上爬的过程中,每爬一次看它在当前节点的儿子序列中排第 个,则说明所在集合胜了 次(这里排列 与之前的描述是相反的/cy),对 有 的贡献。而它胜儿子们还有额外 的贡献,其中 是 的儿子树。这样的表达太难受了,考虑写一个用父亲的 值表达的递推式。容易写出 ,其中 往上爬一次的 。如果再将 的含义 reverse 一次,表达式则简单很多,为 (当然是模 意义下的)。
又注意到:设最终能得到某一个向量 ,其元素的可重集为 ,则任意可重集为 的向量都能达到(只要置换一下元素的地位即可)。这意味着我们可以从可重集的角度出发去计数,但要乘上 ,这要求我们的 DP 是以一种一种的 为阶段的。
下面正式开始 DP。设 为有 个节点、至多 层的所有多叉树的所有可能的可重集的可重集排列数之和。由于以层为阶段,每层的 相等,只有两种可能的 ,极易做到转移时立刻决定 并以其为系数。再仔细想想,其实根本不需要记录 ,直接当作在考虑目前这棵树的最后一层即可,毕竟各层无本质区别(第一层除外,必须恰有一个点,所以要特判 )。
考虑枚举最后一层的 的个数 ,以及 的个数 。考察递推式 ,最后一层 值为 ,所以仅考虑 和 。那么对于倒数第二层的某个节点 ,如果 是偶数,则它的儿子们的 固定, 却有一半是 一半是 ,所以儿子们的 值一定是一半 一半 。一直这样下去的话必有 ,需要 为奇数来调节。类似推理,可以知道这样 的儿子们中 的会比 的多一个。
于是一种方案就是倒数第二层有 个 为奇数的 ,且这些 的 值都要等于 ,偶数点无所谓,但要保证奇偶总共至少有一个节点。只要是存在对应多叉树满足这个条件的向量元素可重集,便可将 个 、 个 接在下面,于是直接转移到对应状态即可。但是有那么一种可能,就是倒数第二层 为奇数的 的个数还可以是大于 且与之奇偶性相同的数 ,并且 的比 的多 个。把这些情况的 DP 值都加在一起吗?对不起,可能有重复。一种理想情况是,存在某一种状态的所有可能可重集完全包含其它状态,那就可以只算这个状态。幸运的是,可以证明 个奇数的状态就是完全包含其它的。因为若超过 ,则必存在两个奇数点的 值不同,则将其中一个的儿子给另一个,该层 值可重集不变,且奇数点减少了两个。
好的,现在将 DP 定义扩展至 表示 个数,最后一层 ,且这 个的 值必须都等于 。重新考虑转移,可以发现相比于之前多了 的影响,之前都是 的。那么设 $c’u=c_u-s_u, 即 可 跟 之 前 差 不 多 。 枚 举 x,y分 别 表 示 s_u为 偶 数 的 点 中 c’=0/1的 数 量 , 则 根 据 j,k容 易 算 出 x’,y’分 别 表 示 所 有 点 中 c’=0/1的 数 量 , 以 及 x’’,y’’分 别 表 示 所 有 点 中 c=0/1的 数 量 。 那 么 贡 献 为 \frac{1}{x’’!y’’!}dp {i-j-x-y,\lvert x’-y’ \rvert,[x’>y’]}$。
这样时间复杂度是 ,可以过 agc 原题,但过不了模拟赛(魔鬼笑)。
先放个四方代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 constexpr int N = 510 ;int n;int iv[N], fc[N], ifc[N];int dp[N][N][2 ];void mian () { n = read (), P = read (); iv[1 ] = 1 ; REP (i, 2 , n) iv[i] = (ll)iv[P % i] * (P - P / i) % P; fc[0 ] = ifc[0 ] = 1 ; REP (i, 1 , n) fc[i] = (ll)fc[i - 1 ] * i % P, ifc[i] = (ll)ifc[i - 1 ] * iv[i] % P; dp[1 ][0 ][0 ] = dp[1 ][0 ][1 ] = dp[1 ][1 ][1 ] = 1 ; REP (i, 2 , n) REP (j, 0 , i - 1 ) REP (k, 0 , 1 ) { REP (x, 0 , i - 1 - j) REP (y, 0 , i - 1 - j - x) if (j || x || y) { int x0 = x + (k == 1 ) * j, y0 = y + (k == 0 ) * j; int x00 = x + (k == 0 ) * j, y00 = y + (k == 1 ) * j; int ad = x0 < y0 ? dp[i - j - x - y][y0 - x0][0 ] : dp[i - j - x - y][x0 - y0][1 ]; addto (dp[i][j][k], (ll)ifc[x00] * ifc[y00] % P * ad % P); } } int ans = dp[n][0 ][0 ]; ans = (ll)fc[n] * ans % P; prt (ans), pc ('\n' ); }
考虑优化到 。
观察代码,枚举 ,考虑分成四元组 和 来查看。
总贡献为 (这里 虽然不在求和枚举里,但也是被枚举的变量)。如果能 知道后面这个 的值,便达到了三方。注意到该 仅与 j || x
、 、x + (k ? j : -j)
、 有关,其中 j || x
是 bool 值其复杂度可以忽略。这样还是涉及三个 的量,有 种 的值(flag),计算每种的话加上枚举 还是四方的复杂度。
但是注意到最后一项 ,如果 就不需要记录了,那么就只有 种,对每种暴力计算复杂度就是三方了。那 呢?很简单,交换 地位即可。
略微卡常,用了 18 次乘法取一次模的优化才过/qd
code:
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 constexpr int N = 510 ;int n;int iv[N], fc[N], ifc[N];int dp[N][N][2 ];ull f[N][3 * N][2 ][2 ]; int vis[N][3 * N][2 ];void mian () { n = read (); iv[1 ] = 1 ; REP (i, 2 , n) iv[i] = (ll)iv[P % i] * (P - P / i) % P; fc[0 ] = ifc[0 ] = 1 ; REP (i, 1 , n) fc[i] = (ll)fc[i - 1 ] * i % P, ifc[i] = (ll)ifc[i - 1 ] * iv[i] % P; dp[1 ][0 ][0 ] = dp[1 ][0 ][1 ] = dp[1 ][1 ][1 ] = 1 ; memset (f, -1 , sizeof (f)); REP (i, 2 , n) REP (j, 0 , i - 1 ) REP (k, 0 , 1 ) { if (k == 0 ) { REP (x, 0 , i - 1 - j) { ull &F = f[i - j - x][x + (k ? j : -j) + n][k][j || x]; if (!~F) { F = 0 ; int c = 0 ; REP (y, 0 , i - 1 - j - x) if (j || x || y) { int x0 = x + (k == 1 ) * j, y0 = y + (k == 0 ) * j; int y00 = y + (k == 1 ) * j; int ad = x0 < y0 ? dp[i - j - x - y][y0 - x0][0 ] : dp[i - j - x - y][x0 - y0][1 ]; F += (ll)ifc[y00] * ad; if (++c == 18 ) F %= P, c = 0 ; } F %= P; } int x00 = x + (k == 0 ) * j; addto (dp[i][j][k], ifc[x00] * F % P); } } else { REP (y, 0 , i - 1 - j) { ull &F = f[i - j - y][y + (!k ? j : -j) + n][k][j || y]; if (!~F) { F = 0 ; int c = 0 ; REP (x, 0 , i - 1 - j - y) if (j || x || y) { int x0 = x + (k == 1 ) * j, y0 = y + (k == 0 ) * j; int x00 = x + (k == 0 ) * j; int ad = x0 < y0 ? dp[i - j - x - y][y0 - x0][0 ] : dp[i - j - x - y][x0 - y0][1 ]; F += (ll)ifc[x00] * ad; if (++c == 18 ) F %= P, c = 0 ; } F %= P; } int y00 = y + (k == 1 ) * j; addto (dp[i][j][k], ifc[y00] * F % P); } } } int ans = dp[n][0 ][0 ]; ans = (ll)fc[n] * ans % P; prt (ans), pc ('\n' ); }
感谢 chenxia25 的题解 。
后记 感觉之前的总结都比较水。今天曾总通过现实反例让我意识到总结不能像记流水账一样。要有自己的看法和反思。