[LuoguP1829]Crash的文明表格(二次扫描与换根+第二类斯特林数)

本文主要是介绍[LuoguP1829]Crash的文明表格(二次扫描与换根+第二类斯特林数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

a.png

Solution:

​ 由于
\[ x^m = \sum_{i=0}^m{~m~\choose i}{~x~\brace i}i! \]
​ 将所求的式子化成这样,挖掘其性质,考虑是否能从儿子转移(或利用以求得信息)。
\[ \begin{aligned} S(u) &= \sum_{i=1}^ndis(u,i)^k\\ &= \sum_{i=1}^n\sum_{j=0}^k{dis(u, i) \choose j}{k\brace j}j!\\ &= \sum_{j=0}^kj!{k\brace j}\sum_{i=1}^n{dis(u, i)\choose j} \end{aligned} \]
​ 由于组合数有:\({n\choose m} = {n - 1\choose m - 1} + {n - 1\choose m}\)

​ 而从儿子及父亲到自己的距离为1,于是可以考虑换根树型dp求出每个点的 \(\sum_{i=1}^n{dis(u, i)\choose j}\)

​ 设 \(f[u][j] = \sum_{i}{dis(u, i) \choose j}\) 其中 \(i\)\(u\) 子树中的点。

​ 设 \(g[u][j] = \sum_{i=1}^n{dis(u, i)\choose j}\)
\[ f[u][j] = \sum_{v\in son(u)}f[v][j] + f[v][j - 1]\\ g[u][j] = g[fa(u)][j-1]-f[u][j-2]-f[u][j-1]+g[fa(u)][j]-f[u][j-1]-f[u][j]+f[u][j] \]

Code

#include <vector>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>typedef long long LL;
typedef unsigned long long uLL;#define fir first
#define sec second
#define SZ(x) (int)x.size()
#define MP(x, y) std::make_pair(x, y)
#define PB(x) push_back(x)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO debug("GO\n")
#define rep(i, a, b) for (register int i = (a), i##end = (b); (i) <= i##end; ++ (i))
#define drep(i, a, b) for (register int i = (a), i##end = (b); (i) >= i##end; -- (i))
#define REP(i, a, b) for (register int i = (a), i##end = (b); (i) < i##end; ++ (i))inline int read() {register int x = 0; register int f = 1; register char c;while (!isdigit(c = getchar())) if (c == '-') f = -1;while (x = (x << 1) + (x << 3) + (c xor 48), isdigit(c = getchar()));return x * f;
}
template<class T> inline void write(T x) {static char stk[30]; static int top = 0;if (x < 0) { x = -x, putchar('-'); }while (stk[++top] = x % 10 xor 48, x /= 10, x);while (putchar(stk[top--]), top);
}
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }using namespace std;const int maxN = 50004;
const int maxK = 153;
const int MOD = 10007;int n, k;
int fac[maxK];
int stirl[maxK][maxK];
vector<int> ver[maxN];void Input()
{n = read(), k = read();for (int i = 1; i < n; ++i){int u = read(), v = read();ver[u].push_back(v);ver[v].push_back(u);}
}void Init() 
{fac[0] = 1;rep (i, 1, k) fac[i] = 1ll * fac[i - 1] * i % MOD;stirl[0][0] = stirl[1][1] = 1;rep (i, 2, k)rep (j, 1, i) stirl[i][j] = (1ll * stirl[i - 1][j - 1] + 1ll * j * stirl[i - 1][j] % MOD) % MOD;
}int f[maxN][maxK], g[maxN][maxK], tmp[maxK];void dfs1(int u, int fa)
{f[u][0] = 1;for (int v : ver[u]) if (v != fa){dfs1(v, u);f[u][0] = (1ll * f[u][0] + f[v][0]) % MOD;for (int j = 1; j <= k; ++j)f[u][j] = ((1ll * f[u][j] + f[v][j]) % MOD + f[v][j - 1]) % MOD;}
}void add(int &x, int y)
{x = (1ll * x + y + MOD) % MOD;
}void dfs2(int u, int fa)
{if (!fa) for (int i = 0; i <= k; ++i) g[u][i] = f[u][i];else {g[u][0] = g[fa][0];for (int j = 1; j <= k; ++j){int &x = g[u][j];x = 0;add(x, g[fa][j]);add(x, -f[u][j]);add(x, -f[u][j - 1]);add(x, g[fa][j - 1]);add(x, -f[u][j - 1]);add(x, f[u][j]);if (j >= 2) add(x, -f[u][j - 2]);}}for (int v : ver[u])if (v != fa)dfs2(v, u);
}void Solve()
{dfs1(1, 0);dfs2(1, 0);for (int i = 1; i <= n; ++i){int ans = 0;for (int j = 0; j <= k; ++j)ans = (1ll * ans + 1ll * stirl[k][j] * fac[j] % MOD * g[i][j] % MOD) % MOD;cout << ans << endl;}
}int main() 
{
#ifndef ONLINE_JUDGEfreopen("tmp.in", "r", stdin);freopen("tmp.out", "w", stdout);
#endifInput();Init();Solve();return 0;
}

转载于:https://www.cnblogs.com/cnyali-Tea/p/11439945.html

这篇关于[LuoguP1829]Crash的文明表格(二次扫描与换根+第二类斯特林数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/247200

相关文章

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

Java利用poi实现word表格转excel

《Java利用poi实现word表格转excel》这篇文章主要为大家详细介绍了Java如何利用poi实现word表格转excel,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、每行对象类需要针对不同的表格进行对应的创建。package org.example.wordToEx

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

使用Python实现表格字段智能去重

《使用Python实现表格字段智能去重》在数据分析和处理过程中,数据清洗是一个至关重要的步骤,其中字段去重是一个常见且关键的任务,下面我们看看如何使用Python进行表格字段智能去重吧... 目录一、引言二、数据重复问题的常见场景与影响三、python在数据清洗中的优势四、基于Python的表格字段智能去重

如何利用Python实现给Excel表格截图

《如何利用Python实现给Excel表格截图》这篇文章主要为大家详细介绍了如何利用Python实现给Excel表格截图功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 我搜索了网络上的方案,感觉把 Excel 表格转换为 html 再用 platwright 截图是比China编程较顺

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

SQL注入漏洞扫描之sqlmap详解

《SQL注入漏洞扫描之sqlmap详解》SQLMap是一款自动执行SQL注入的审计工具,支持多种SQL注入技术,包括布尔型盲注、时间型盲注、报错型注入、联合查询注入和堆叠查询注入... 目录what支持类型how---less-1为例1.检测网站是否存在sql注入漏洞的注入点2.列举可用数据库3.列举数据库

使用SQL语言查询多个Excel表格的操作方法

《使用SQL语言查询多个Excel表格的操作方法》本文介绍了如何使用SQL语言查询多个Excel表格,通过将所有Excel表格放入一个.xlsx文件中,并使用pandas和pandasql库进行读取和... 目录如何用SQL语言查询多个Excel表格如何使用sql查询excel内容1. 简介2. 实现思路3

IDEA常用插件之代码扫描SonarLint详解

《IDEA常用插件之代码扫描SonarLint详解》SonarLint是一款用于代码扫描的插件,可以帮助查找隐藏的bug,下载并安装插件后,右键点击项目并选择“Analyze”、“Analyzewit... 目录SonajavascriptrLint 查找隐藏的bug下载安装插件扫描代码查看结果总结Sona