首页 > 其他分享 >【YBT2023寒假Day1 C】对峙绝望(数学)(第二类斯特林数)(NTT)

【YBT2023寒假Day1 C】对峙绝望(数学)(第二类斯特林数)(NTT)

时间:2023-01-28 21:45:31浏览次数:67  
标签:return int mo YBT2023 invs NTT Day1 mul inv

对峙绝望

题目链接:YBT2023寒假Day1 C

题目大意

定义一个无向图的权值是所有结点度数的 k 次方之和。(规定 0 的 0 次方是 1)
求所有 n 个点的简单无向图的权值之和。
对 998244353 取模。

思路

首先会发现每个点其实是一样的(除了编号),那我们可以只求出一个的贡献,然后总答案就是一个的 \(*n\)。

然后因为 \(n\) 太大一个 \(d^k\) 下面太大了,我们考虑用第二类斯特林数进行分解:
\(d^k=\sum\limits_{i=0}^kS(k,i)C(d,i)i!\)
(\(d^k\) 相当于 \(k\) 个有标号球放入 \(d\) 个有标号的桶)
(然后 \(S(k,i)\) 是 \(k\) 个有标号球放入 \(i\) 个无标号桶且每个桶非空)
(然后枚举非空桶的数量,然后再 \(C(d,i)\) 看是哪些桶,然后再用 \(i!\) 给选了的桶标号)

那你就变成对于 \(1\sim k\) 的每个 \(i\),你要求所有简单无向图中 \(1\) 号点连的边中选出 \(i\) 条的方案数之和。
考虑反置一下要求,先选出 \(i\) 条边,再看别的边选不选(那这些任选)。
也就是 \(C(n-1,i)2^{n(n-1)/2-i}\)(注意是 \(C(n-1,i)\) 因为跟 \(1\) 号点连边的边数是 \(n-1\))
那我们设这个东西是 \(Sum_i\),那我们要的答案其实就是:
\(\sum\limits_{i=0}^kS(k,i)Sum_ii!\)

那剩下的问题就是如何预处理 \(S(k,i)\),那这是一个经典的第二类斯特林数行的问题,用容斥:
\(m!S(n,m)=\sum\limits_{i=0}^m(-1)^{m-i}C(m,i)i^n\)
拆开组合数:
\(m!S(n,m)=m!\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\dfrac{i^n}{i!}\)
\(S(n,m)=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\dfrac{i^n}{i!}\)
那这个就是一个卷积的形式,直接 NTT 就好了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mo 998244353
#define ll long long
#define clr(f, x) memset(f, 0, sizeof(int) * (x))
#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))

using namespace std;

const int N = 5e5 + 100;
const int pN = N * 8;
int n, k, jc[N], inv[N], invs[N], S[N];
int f[pN], g[pN];

int add(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {return 1ll * x * y % mo;}
int ksm(int x, ll y) {
	int re = 1;
	while (y) {
		if (y & 1) re = mul(re, x);
		x = mul(x, x); y >>= 1;
	}
	return re;
}
int C(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return mul(mul(jc[n], invs[m]), invs[n - m]);
}

struct Poly {
	int an[pN], G = 3, Gv;
	
	void Init() {
		jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = mul(jc[i - 1], i);
		inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = mul(inv[mo % i], mo - mo / i);
		invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = mul(invs[i - 1], inv[i]);
		Gv = ksm(G, mo - 2);
	}
	
	void get_an(int limit, int l_size) {
		for (int i = 0; i < limit; i++)
			an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1));
	}
	
	void NTT(int *f, int limit, int op) {
		for (int i = 0; i < limit; i++)
			if (i < an[i]) swap(f[i], f[an[i]]);
		for (int mid = 1; mid < limit; mid <<= 1) {
			int Wn = ksm(op == 1 ? G : Gv, (mo - 1) / (mid << 1));
			for (int j = 0, R = (mid << 1); j < limit; j += R)
				for (int w = 1, k = 0; k < mid; k++, w = mul(w, Wn)) {
					int x = f[j | k], y = mul(w, f[j | mid | k]);
					f[j | k] = add(x, y); f[j | mid | k] = dec(x, y);
				}
		}
		if (op == -1) {
			int limv = ksm(limit, mo - 2);
			for (int i = 0; i < limit; i++) f[i] = mul(f[i], limv);
		}
	}
	
	void px(int *f, int *g, int limit) {
		for (int i = 0; i < limit; i++)
			f[i] = mul(f[i], g[i]);
	}
	
	void times(int *f, int *g, int n, int m, int T) {
		int limit = 1, l_size = 0; while (limit < n + m) limit <<= 1, l_size++;
		get_an(limit, l_size);
		static int tmp[pN]; clr(f + n, limit - n); cpy(tmp, g, m); clr(tmp + m, limit - m);
		NTT(f, limit, 1); NTT(tmp, limit, 1); px(f, tmp, limit); NTT(f, limit, -1);
		clr(f + T, limit - 1); clr(tmp, limit);
	}
}P;

void getS() {
	for (int i = 0; i <= k; i++) {
		f[i] = mul((i & 1) ? mo - 1 : 1, invs[i]);
		g[i] = mul(ksm(i, k), invs[i]);
	}
	P.times(f, g, k + 1, k + 1, k + 1);
	for (int i = 0; i <= k; i++)
		S[i] = f[i];
}

int main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	
	P.Init();
	scanf("%d %d", &n, &k);
	
	getS();
	int ans = 0, CC = 1, inv2 = ksm(2, mo - 2), sum2 = ksm(2, 1ll * n * (n - 1) / 2);
	for (int i = 0; i <= k; i++) {
		ans = add(ans, mul(S[i], mul(mul(CC, mul(sum2, ksm(inv2, i))), jc[i])));
		CC = mul(CC, mul(n - 1 - i, inv[i + 1]));
	} 
	printf("%d", mul(ans, n));
	
	return 0;
}

标签:return,int,mo,YBT2023,invs,NTT,Day1,mul,inv
From: https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day1_C.html

相关文章

  • 【YBT2023寒假Day1 B】不跪模样(树链剖分)(线段树)
    不跪模样题目链接:YBT2023寒假Day1B题目大意给你一棵有根数,点有点权,两种操作:对于所有x子树内与x距离不超过2的点,将其点权加v。询问x子树中,满足i<=j且i,j......
  • 【YBT2023寒假Day1 A】孤走暗巷(费用流)
    孤走暗巷题目链接:YBT2023寒假Day1A题目大意给你一个整数序列,你要通过一些操作把它变成单调不降序列。你有m种操作,每次可以选择一个长度为li的区间,花费ci的代价......
  • 《RPC实战与核心原理》学习笔记Day11
    13|优雅关闭:如何避免服务停机带来的业务损失?我们在RPC架构下,需要考虑当服务重启时,如何做到让调用方系统不出问题。当服务提供方要上线时,一般是通过部署系统完成实例重......
  • 「WC-2023」学习笔记(Day1&2)
    尼玛在游记里立flag是吧。1月必更新是吧。寒假作业都写不完了!!!!!这篇四舍五入就是1月学习记录了。1月剩下的杂题可能放2月去写。嗯也可能2月就退役了。退役了就没......
  • day11-实现Spring底层机制-01
    实现Spring底层机制-01主要实现:初始化IOC容器+依赖注入+BeanPostProcessor机制+AOP前面我们实际上已经使用代码简单实现了:SpringXML注入bean(Spring基本介绍02)Sp......
  • C++Day13 tinyxml2解析rss文件
    一、任务与思路使用tinyxml解析rss文件,使用std::regex(正则表达式)去除html标签,并生成一个pagelib.txt,格式如下<doc><docid>1</docid><title>...</title><......
  • PLC笔记 知识点汇总 day1
          blog:师万物 本文是学习内容的简单回顾,希望对大家能有所帮助。 电路直流蓄电池交流单相(两线、三相)、两相、三相(三线、四线、五线)发电机:......
  • 《RPC实战与核心原理》学习笔记Day10
    11|负载均衡:节点负载差距这么大,为什么收到的流量还一样?什么是负载均衡?当我们的一个服务节点无法支撑现有的访问量时,我们会部署多个节点,组成一个集群,然后通过负载均衡,......
  • day12
    1、leetcode239滑动窗口最大值思路:使用一个队列,将窗口里的元素放入队列,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。队列所需......
  • Day19 - 正则表达式
    正则表达式的概述正则表达式的介绍在实际开发过程中经常会有查找符合某些复杂规则的字符串的需要,比如:邮箱、图片地址、手机号码等,这时候想匹配或者查找符合某些规则的......