首页 > 其他分享 >AGC022F 做题记录

AGC022F 做题记录

时间:2024-04-08 21:44:25浏览次数:31  
标签:... space ll 记录 maxn AGC022F mod define

link

很牛逼的题目。

操作 \(A,B\),考虑从 \(A\) 向 \(B\) 连一条边,最终形成一棵内向有根树。

所有次项的系数都是 \(2^p(-1)^q\) 的形式。对于树上的一个点 \(u\),不难发现 \(u\) 的深度是 \(2\) 的次数。

设 \(c_{d,0/1}\) 表示深度为 \(d\) 的点中系数为 \(1/-1\) 的点的个数,那么对应状态下的方案数为 \(\dbinom{n}{c_{0,0}\space c_{0,1}\space c_{1,0}\space c_{1,1}\space c_{2,0}\space c_{2,1}\space ...}\)。

  • 一个重要的 Trick:直接考虑 \(c_{1...n-1,0/1}\) 合法的充要条件

我们考虑直接模拟建树还原的过程:\(c_{d,1-x}\) 可以和 \(c_{d+1,x}\) 合并成 \(c_{d,x}\),具体操作是把一个点的第一个儿子删除。

换句话讲,就是 \(c_{d,1-x}\) 可以花费一个 \(c_{d+1,x}\) 转为 \(c_{d,x}\)。因此,根据贪心思想,\(c_{d,0}\) 和 \(c_{d,1}\) 可以 互相抵消。

设 \(f[i,j]\) 表示 \(i\) 个点的森林,还原之后 \(c_{\_,0}-c_{\_,1}\) 的值为 \(j\),的方案数。转移容易。

总结一下:

  • 抽象过程需要模型转化。

  • 直接考虑充要条件,避免过多的讨论。

  • 仔细观察整个过程,模拟过程,然后 dp。

  • dp 的状态需要结合贪心。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=52, mod=1e9+7;
ll n,f[maxn][maxn<<1],c[maxn][maxn];
void add(ll &x,const ll y) {x=(x+y>=mod? x+y-mod:x+y);}
int main(){
	scanf("%lld",&n);
	c[0][0]=1;
	for(ll i=1;i<=n;i++){
		c[i][0]=1;
		for(ll j=1;j<=n;j++)
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	for(ll i=1;i<n||i<=1;i++)
		for(ll j=0;j<=i;j++)
			f[i][j-(i-j)+n]=c[i][j];
	for(ll i=2;i<=n;i++)
		for(ll j=0;j<i;j++)
			for(ll k=(j==0);j+k<i;k++){
				if(i==n&&j+k>1) continue;
				for(ll x=0;x<=i-j-k&&x<=k;x++)
					add(f[i][j-k+2*x+n],f[i-j-k][x+n]*c[j+k][j]%mod*c[i][j+k]%mod);
				for(ll x=1;x<=i-j-k&&x<=j;x++)
					add(f[i][j-k-2*x+n],f[i-j-k][n-x]*c[j+k][j]%mod*c[i][j+k]%mod);
			}
	printf("%lld",f[n][n+1]);
	return 0;
}

标签:...,space,ll,记录,maxn,AGC022F,mod,define
From: https://www.cnblogs.com/Sktn0089/p/18122687

相关文章

  • 2024年4月 杂题记录
    P10322高洁(Purity)设\(d=\prodp_i^{c_i}\),容易发现当\(d\midi^k\)时,\(i^k\)的所有质因子的幂次都不小于\(d\)的所有所有质因子的幂次,即\(i^k\)含有的质因子的幂次至少为\(\lceilc_i/k\rceil\),因此我们设\[f_k(d)=\prodp_i^{\lceilc_i/k\rceil}\]那么就有\(d\mid......
  • 井字棋-C语言(学习记录)
     一:游戏简介     井字棋,英文名叫Tic-Tac-Toe,是一种在3*3格子上进行的连珠游戏,和五子棋类似,由于棋盘一般不画边框,格线排成井字故得名。游戏需要的工具仅为纸和笔,然后由分别代表O和X的两个游戏者轮流在格子里留下标记(一般来说先手者为X),任意三个标记形成一条直线,则为获......
  • 哈希表自记录
    存储结构:1.开放寻址法#include<cstring>#include<iostream>usingnamespacestd;constintN=2000003,null=0x3f3f3f3f;inth[N];intn;intfind(intx){intk=(x%N+N)%N;//蹲坑法while(h[k]!=null&&h[k]!=x){k++;......
  • 【SVN】安装记录
    VisualSVNhttps://www.visualsvn.com/downloads/  TortoiseSVNTortoiseSVN官网打不开,去哪下最新的软件和中文包?官网:https://tortoisesvn.net能打开最好,但通常打不开,打不开时候去这个网站下;https://sourceforge.net/projects/tortoisesvn/这个网站开发软件的应该很熟......
  • AndroidStudio学习记录(5):图像按钮ImageView的实现
    <?xmlversion="1.0"encoding="utf-8"?><LinearLayoutxmlns:android="http://schemas.android.com/apk/res/android"android:layout_width="match_parent"android:layout_height="match_parent"......
  • Blazor学习记录_12._IIS部署_组件的引用_
    27.Blazor项目发布与IIS部署27.1如果是Auto模版的项目,选择两个项目中的Server项目进行发布27.2服务器必要的运行时安装与配置1.安装运行时可先通过命令行输入:dotnet--info来查看本地已经安装的运行时情况。运行时官方下载页面:https://dotnet.microsoft.com/zh-cn/dow......
  • Unity类银河恶魔城学习记录12-7-2 p129 Craft UI - part 2源代码
    Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibiliUI_CraftWindow.csusingUnityEngine.UI;usingTMPro;usingUnityEngine;usingU......
  • DNS 各记录类型说明及规则
    各记录类型使用目的记录类型使用目的A记录将域名指向一个IP地址。CNAME记录将域名指向另一个域名,再由另一个域名提供IP地址。MX记录设置邮箱,让邮箱能收到邮件。NS记录将子域名交给其他DNS服务商解析。AAAA记录将域名指向一个IPv6地址。SRV记录用来标识某台服......
  • Acwing 681. 疏散人群(dfs)(记录根节点下有几个子节点)
    输入样例:62132435261输出样例:4#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;constLLN=100200,M=2020;constLLmod=998244353;vector<LL>g[N];LLsum[N];LLdfs(LLidx,LLfa){LL......
  • 记录linux从0部署java项目(宝塔)
    目录一、安装宝塔可视化界面 二、部署前端三、部署后端1、配置并连接Mysql数据库2、配置并连接redis3、安装jdk这里先记录一个安装后遇到的问题安装openJDK四、检查一、安装宝塔可视化界面宝塔面板下载,免费全能的服务器运维软件运行安装脚本安装完成后访问......