首页 > 其他分享 >南外集训 2024.1.12 T3/AGC022F Checkers 加强版

南外集训 2024.1.12 T3/AGC022F Checkers 加强版

时间:2024-01-14 20:57:16浏览次数:45  
标签:一层 2024.1 12 Checkers 奇数 符号 个数 儿子 DP

第一步转化比较套路,DP 设计需要很强的洞察力,最后的优化也很考验基本功。

有 \(n\) 个 \(n\) 维空间中的点,第 \(i\) 个点 \(x_i\) 满足 \(x_{i,i} = 1, x_{i, j} = 0(\forall i\neq j)\)。接下来进行 \(n - 1\) 次操作,每次任选两个点,将第一个点关于第二个点对称,然后删掉第二个点。求最后剩下点的坐标有多少种。答案对 \(M\) 取模。

\(1\le n\le 500, 10^4+7\le M\le 10^9+7\),且 \(M\) 是素数。

只需要考虑每个点的系数。注意到这个系数只会是 \(\pm 2^d\),也就是我们只关心在整个过程中它被作为第二个点合并了多少次,以及他被作为第一个点合并了奇数还是偶数次。将每一次合并的第二个数按照顺序挂在第一个数下面,形成一棵树,那么 \(d\) 就是这个点的深度,\(-1\) 的次数就是【它的儿子个数】加上【它到根的链上所有右侧的兄弟个数】。

考虑用 DP 做计数。在加入一层时需要知道当前层符号为 \(-1\) 和 \(+1\) 的具体个数。注意到一个点的符号还和自己的儿子个数有关,所以需要在 DP 状态中记录有关那些儿子个数为奇数的点的信息,然后在下一层满足这些要求。

注意到,如果一个点的儿子个数是偶数,那么在不考虑更下一层的情况下,所有它的儿子恰好有一半和它符号相同,一半和它相反,所以我们并不关心这个点的符号到底是什么,实际上我们只关心有多少个点被挂在了偶数子树下,全部这些点中的一半符号是 \(-1\),一半是 \(1\)。而有奇数个儿子的点,可以把第一个儿子拆出来,后面的点也是一半一半分布。所以我们事实上只关心上一层有多少奇数个儿子的点,以及这些点的符号是什么。进一步思考,如果这些奇数个儿子的点中,既存在符号为 \(-1\) 的又存在符号为 \(1\) 的,那么直接把其中一个的第一个儿子摘下来挂到另一个上面,那么上一层和这一层的 \(-1\) 和 \(1\) 个数都完全不变,如果我们先不急着分配标号,就会发现这样调整完全不影响计数。所以可以直接要求上一层所有有奇数个儿子的所有点,它们的符号都一样。

有了上一段的一系列强有力的结论,我们可以设计出 DP 状态:\(f_{i,j}\) 表示前几层总共 \(i\) 个元素,最后一层有 \(j\) 个点希望有奇数个儿子。不妨设上一层有奇数个儿子的这些点最终的符号都是 \(+\),那么它的儿子的原始符号是 \(-\),总共个 \(j\),同时枚举下一层还有 \(x\) 对 \(\pm 1\),这样我们得到了 \(x+j\) 个 \(-\) 和 \(x\) 个 \(+\),我们接下来枚举有 \(y\) 个 \(-\) 被转变成 \(+\)(\(y<0\) 表示有 \(+\) 被转变为 \(-\)),这样 \(y\in [-x, x+j]\)。我们最终获得了 \(j+x-y\) 个 \(-\) 和 \(x+y\) 个 \(+\),发生转变的点也就是有奇数个儿子的点个数是 \(|y|\)。那么写出转移方程:

\[\frac{1}{(j+x-y)!(x+y)!}\cdot f_{i, j} \to f_{i+j+2x, |y|} \]

方便起见我们拆掉组合数,最后再乘以 \(n!\) 即可。

这里我们已经得到了一种 \(\Theta(n^4)\) 做法,当然不能通过。接下来我们要通过分步预处理将这个 DP 优化成 \(\Theta(n^3)\)。考虑对于每个 \(f_{i,j}\),枚举 \(x-y = d_1\),将 \(\frac{1}{(j+d_1)!}\cdot f_{i,j}\) 贡献到 \(g_{i+j, x-y}\),接下来枚举 \(g_{s, d_1}\) 以及 \(d_2 = x+y\),这时候我们可以通过 \(d_1, d_2\) 算出 \(x,y\) 的具体数值,将 \(\frac{1}{d_2!}\cdot g_{s, d_1}\) 贡献到 \(f_{s+2x,|y|}\)。时间复杂度 \(\Theta(n^3)\)。

标签:一层,2024.1,12,Checkers,奇数,符号,个数,儿子,DP
From: https://www.cnblogs.com/kyeecccccc/p/17964166

相关文章

  • 本周(2024.1.8-2024.1.14)C语言学习小结
    既然之前说了要尝试坚持写博客,那就试试吧。本周花在C语言上的时间不多,简要回顾一下。动态数组学习并实践了基本的动态数组知识,即calloc、malloc、relloc、free。以下是基本综合所学内容写的代码,实现动态数据添加。#include<stdio.h>#include<stdlib.h>intmain(){......
  • 2024.1.14-每日进度笔记
    今天,我主要尝试了对之前的几个python脚本进行整合,使得可以输入图片路径,题目,总分进行评价 参考:百度文心一言的回复 #-*-coding:utf-8-*-importosimportsysimporterniebotfromPILimportImagefrompaddleocrimportPaddleOCR,draw_ocrdefbaidu_paddleocr......
  • [刷题班] LeetCode125. 验证回文串
    题目描述思路:左右指针只考虑数字和字母字母的话需要全部转化为小写然后使用左右指针判断是否是回文串方法一:classSolution{publicbooleanisPalindrome(Strings){List<Character>list=newArrayList<>();for(charc:s.toCharArray()){......
  • [CF1268D] Invertation in Tournament
    InvertationinTournament题面翻译给定一张\(n\)个点的竞赛图,定义一次操作为选取一个顶点\(v\)并翻转所有以\(v\)为顶点的边的方向。请你判断是否存在一种操作方案使得操作完成后,这个图是强连通的。如果存在,求出最小的操作次数,以及使得操作次数达到最小的操作方案数。其......
  • 【公开课-微软RPA】12月23日,RPA 学习天地成功举办基于微软RPA公开课,让更多人用上RPA,用
    12月23日,RPA学习天地成功举办了,基于微软RPA工具(PowerAutomateDesktop)直播公开课,成功地帮助学员们初步了解了微软RPA工具的功能。本次公开课,主要介绍了如何使用微软的RPA工具来实现Boss直聘岗位薪资自动爬取的场   首先:通过查询岗位相关信息并保存到本地,然后进行数据筛......
  • 2023.9 ~ 2024.1 总结
    前言本文没有知识总结,只记录一些本学期思维上提升的和对自己学习状态的总结(当然知识总结也是有的,但是我太菜了,还不全面)1.个人习惯反思可跳过,主要写给自己一个学期过去了,成长还是有的,但是还是两个老毛病:浮躁,静不下心心态不稳听课情景1:听课时想要记笔记,然后就跟......
  • CF1201C - Maximum Median
    思路二分答案。对于一个mid,查询中位数要是为mid的话至少要做多少次操作,最小操作次数就是排序后从中位数开始计算max(0,mid-v[i])的和ac代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;consti64inf=8e18;typedefpair<int,int>pii;cons......
  • AT_arc125_c [ARC125C] LIS to Original Sequence 题解
    题目传送门前置知识贪心|构造解法对于任意一个未加入序列\(P\)的数\(x<A_{i}(1\lei\lek-1)\),如果其放在了\(A_{i}\)的前面,会导致最长上升子序列长度加一,从而不符合题目要求。因此我们需要把\(x\)放在\(A_{i}\)后面,同理,为符合题目要求,我们仅选择放最小的那一个......
  • CF1284E New Year and Castle Construction
    NewYearandCastleConstructionLuoguCF1284E题目描述给定大小为\(N\)的点集\(S\)。保证点集中的任意三点不共线,且不存在重复的点。设\(f(p)\)表示满足如下条件的\(S\)的四元子集\(T\)的个数:\(T\subsetS\\landp\notinT\)\(T\)中的元素能组成一个四边形,......
  • 2024.1.13-每日进度笔记
    今天,主要尝试了在java中调用已有的python脚本并输出相关信息。 参考:百度文心一言的回复。 packagetest0113;importjava.io.*;publicclasstest{publicstaticvoidmain(String[]args){try{//指定Python解释器的路径S......