首页 > 其他分享 >abc321记录

abc321记录

时间:2023-09-25 17:57:26浏览次数:42  
标签:连边 连通 ch cnta 记录 方案 mo abc321

SuntoryProgrammingContest2023(AtCoder Beginner Contest 321) - AtCoder

D

题意:给定常数 \(k\) 和长度为 \(n\) 的数组 \(a\) 和长度为 \(m\) 的数组 \(b\),求 \(\sum_{i=1}^n\sum_{j=1}^mmin\{a_i+b_j,k\}\) 。

数据范围:\(n,m \le 2\times10^5\)

tag : 二分 前缀和

枚举 \(a_i\),在 \(b\) 上二分 \(k-a_i\),找到的位置前面的前缀和后面的全是 \(k\) 。

E

题意:多个询问,每个询问给定 \(n\) 个点,根为 \(1\) 的一棵树,节点 \(u\) 的父亲为 \(\left\lfloor\frac{u}2\right\rfloor\),求与节点 \(v\) 距离为 \(k\) 的点的个数。

数据范围:\(k \le n \le 10^{18}\)

tag : 完全二叉树 树形dp

考虑类似换根dp的过程,设 \(g(u,k)\) 为 \(u\) 子树中距离为 \(k\) 的点,这在完全二叉树上显然可以快速计算,计算当前点的答案 \(f(u, k)\) 时实际上是父亲的答案减去在自己子树里多算的部分,\(\begin{cases}f(u,k)=g(u,k)+f(fa,k-1)-g(u,k-2)\\f(1,k)=g(1,k)\end{cases}\),因为树高 \(O(\log n)\),直接向上暴力计算,注意最底层不满的 corner case 。

F

题意:\(n\) 个操作,每个操作在可重集 \(S\) 中加入或删除一个元素 \(k\) ,求每次操作后选取一个子集 \(S'\) 使得 \(\sum_{k\in S'}=m\) 的方案数。

数据范围:\(n,m \le 5000\)

tag : 背包 线段树分治

回退背包板子,注意加入顺序从大到小,回退顺序从小到大。但是赛时线段树分治直接艹过去了

G

题意:给定长度为 \(m\),值域为 \([1, n]\) 的数组 \(a, b\),对于每个 \(i\) 都对应一个互不相同的 \(j\),代表在图上编号为 \(a_i\) 的点向编号为 \(b_j\) 的点连一条双向边,求在所有的连边方式中图的连通块个数的期望。

数据范围:\(m\le10^5,n\le17\)

tag : 状压dp,容斥

赛后补题,参考了一定的lg题解。

显然总的连边方案数是确定的 \(m!\),那么考虑拆分每个连通块的贡献,计算每个连通块在所有连边方式中出现的次数。

注意到 \(n \le17\),考虑状压,设 \(f_S\) 表示点集 \(S\) 只有内部连边并形成至少一个连通块的方案数,\(g_S\) 表示点集 \(S\) 只有内部连边并形成恰好一个连通块的方案数,显然 \(f\) 是易求的,设 \(cnta_S,cntb_S\) 分别表示 \(S\) 的元素在 \(a, b\) 中出现的次数,当 \(cnta_S=cntb_S\) 时,\(S\) 内部可以随便连边,否则,必然有一条边连接 \(S\) 内部的点和外部的点,所以有:\(f_S=[cnta_S=cntb_S]\times cnta_S!\)

接下来考虑通过 \(f\) 求出 \(g\),显然可以容斥:\(S\) 形成恰好一个连通块的方案数等于形成至少一个连通块的方案数减形成多于一个连通块的方案数。而多于一个连通块的方案数显然等于一个子集形成恰好一个连通块的方案数乘以它关于 \(S\) 的补集形成至少一个连通块的方案数。这就可以写成转移方程了:\(g_S=f_S-\sum_{T\subsetneq S}g_T \times f_{S-T}\)

求完 \(g\) ,统计答案时还要乘上 \(S\) 外部随便连边的方案数:\(ans=\frac{\sum g_S \times (m-cnta_S)!}{m!}\)

贴个代码

#include <bits/stdc++.h>
#define pb push_back
#define rg register
#define il inline
using namespace std;
typedef long long ll;
//char buf[1<<21],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1<<17, mo = 998244353;
int i, j, k, l, r, m, n, ans;
int a[N], b[N], fc[N], f[N], g[N];
il int read()
{
    int x = 0, flag = 1;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * flag;
}
int qp(int a, int b=mo-2)
{
	int res = 1;
	for (a%=mo ; b; b>>=1, a=1ll*a*a%mo) if (b&1) res = 1ll * res * a % mo;
	return res;
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
	n = read(), m = read();
	for (fc[0]=i=1; i<=m; i++) fc[i] = 1ll * i * fc[i-1] % mo;
	for (i=1; i<=m; i++) a[read()-1]++;
	for (i=1; i<=m; i++) b[read()-1]++;
	for (k=1; k<(1<<n); k++)
	{
		int sa = 0, sb = 0, p = -1;
		for (i=0; i<n; i++) if (k>>i&1) sa += a[i], sb += b[i], p = ~p ? p : i;
		if (sa != sb) continue;
		g[k] = f[k] = fc[sa];
		for (i=k; i; i=i-1&k) if (i!=k && i>>p&1) g[k] = (g[k] - 1ll * g[i] * f[i^k] % mo + mo) % mo;
		ans = (ans + 1ll * g[k] * fc[m-sa] % mo) % mo;
	}
	printf("%d", 1ll*ans*qp(fc[m])%mo);
    return 0;
}

标签:连边,连通,ch,cnta,记录,方案,mo,abc321
From: https://www.cnblogs.com/luckyluoqwq/p/17728476.html

相关文章

  • ESXI6.7升级7.0u3过程记录
    ESXI6.7升级7.0u3过程记录对ESXI集群进行了EOS升级,从6.7升级至7.0u3,简单记录一下过程,方便以后回顾回溯。vCenter升级整个集群升级的过程中,需要对vc进行升级,VC是可以向下兼容的,先将6.7的vc升级到7.0,由7.0vc对6.7的ESXI主机进行管理。整个升级的过程也比较傻瓜式,对原VC打了内存......
  • 记录返回上一页滚动条的位置
    scrollBehavior可以记录滚动条位置,也可以自己设定滚动条位置constrouter=createRouter({//createRouter返回一个router实例history:createWebHistory(),scrollBehavior:(to,from,savePosition)=>{if(savePosition){returnsavePosition;......
  • 多通道振弦数据记录仪在预防地质灾害中的重要性
    多通道振弦数据记录仪在预防地质灾害中的重要性地质灾害是指在地表或岩体内部发生的、由地质原因引起的、对人类生命、财产和环境安全造成威胁或损害的各种灾害。地质灾害的预测和预防对于保障人民生命财产安全、维护社会稳定和可持续发展具有重要的意义。而多通道振弦数据记录仪......
  • JOISC做题记录
    题目真的很好!!!所以来写一写。但都是一句话题解,因为我实在很懒。打*的是没独立做出来的。慢慢补,不急2023Day1T1TwoCurrencies签到题。主席树上二分就行。$O((n+Q)\logn)$。*2023Day1T2FestivalsinJOIKingdom2还不会。2023Day1T3Passport走遍$1\simn$显然......
  • zTree使用记录
    <linkhref="zTree/zTreeStyle/zTreeStyle.css"rel="stylesheet"/><divid="treeDemo"class="ztree"></div><scriptsrc="zTree/jquery.ztree.all.js"type="text/javascript"><......
  • 文心一言——试用记录
    问题:你是一名专业的原画师,请画一幅坐在咖啡厅的少女给我当头像。     加入“性感”二字,生成失败:    保持关键词:咖啡厅、少年,生成的图片基本一样:请画一幅坐在咖啡厅的少女给我当头像     ==============================......
  • 【问题记录】基于VINS前端构建VO的过程
    【1】图片先去畸变再追踪可以平滑轨迹【2】opencv封装好的solvePNP精度不够,通过G2O优化计算结果更为准确,且必须多轮迭代通过卡方剔除大误差点【3】通过增大特征点的最小间距,保证特征点提取的均匀性【4】setMask函数会对vector进行重新排序......
  • NOIP2023板刷记录
    目录NOIP2023板刷记录CodeforcesCodeforcesRound895(Div.3)PinelyRound2(Div.1+Div.2)A~ECodeforcesRound425(Div.2)CodeforcesRound888(Div.3)AtCoderAtCoderBeginnerContest133AtCoderBeginnerContest312NOIP2023板刷记录CodeforcesCodeforcesRou......
  • C语言学习记录---函数4
    汉诺塔问题(递归)#include<stdio.h>//定义汉诺塔函数voidhanoi(intn,charA,charB,charC){if(n==1){printf("将盘子从%c移动到%c\n",A,C);}else{//将n-1个盘子从A移动到Bhanoi(n-1,A,C,B);//将第n个盘子从......
  • 尚观6410开发板移植linux 3.6.6问题记录及经验小结
    原文:https://www.cnblogs.com/iwantcomputer/p/8489831.html尚观6410开发板移植linux3.6.6问题记录及经验小结把开发板右上角的红色启动选项开关,两个都拨到下面(NAND),连接串口,已经内置了uboot1.16。根文件系统使用ext2的ramdisk,由于网卡无法驱动故无法使用nfs的根文件系统,网卡......