【AtCoder】AGC005F - Many Easy Problems
2024-08-26 03:03:05
题解
我们把一个点的贡献转化为一条边的贡献,因为边的数量是点的数量-1,最后再加上选点方案数\(\binom{n}{k}\)即可
一条边的贡献是\(\binom{n}{k} - \binom{a}{k} - \binom{n - a}{k}\)就是在n个点里选k个点,去掉不合法的情况也就是k个点都在去掉这条边的两个子树里
然后我们要统计的就是\(\binom{a}{k} + \binom{n - a}{k}\)
这个可以转化成\(ans_{k} = \sum_{i = 1}^{n} b_{i} \binom{i}{k}\)
\(ans_{k} = \frac{1}{k!} \sum_{i = 1}^{n} b_{i} i! \frac{1}{(i - k)!}\)
这个数组是可以卷积的,只要把一个倒过来就行
设\(f(i) = \frac{1}{(n - i)!}\)
\(g(i) = b_{i}i!\)
\(h = g * f\)
\(ans_{k} = h(N + k)\)
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
//#define ivorysi
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mo 974711
#define RG register
#define MAXN 200005
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int to,next;
}E[MAXN * 2];
int head[MAXN],sumE;
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
const int MOD = 924844033,L = (1 << 19),G = 5;
int N,f[L + 5],fac[MAXN],invfac[MAXN],b[L + 5],W[L + 5];
int mul(int a,int b) {return 1LL * a * b % MOD;}
int inc(int a,int b) {a = a + b;if(a >= MOD) a -= MOD;return a;}
int fpow(int x,int c) {
int t = x,res = 1;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
int C(int n,int m) {
if(n < m) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n - m]);
}
int dfs(int u,int fa) {
int siz = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa) {
siz += dfs(v,u);
}
}
if(fa != 0) {
b[siz]++;
b[N - siz]++;
}
return siz;
}
void NTT(int *a,int LEN,int on) {
for(int i = 1 , j = LEN / 2 ; i < LEN - 1 ; ++i) {
if(i < j) swap(a[i],a[j]);
int k = LEN / 2;
while(j >= k) {
j -= k;
k >>= 1;
}
j += k;
}
for(int h = 2 ; h <= LEN ; h <<= 1) {
int wn = W[(L + on * L / h) % L];
for(int k = 0 ; k < LEN ; k += h) {
int w = 1;
for(int j = k ; j < k + h / 2 ; ++j) {
int64 u = a[j],t = 1LL * a[j + h / 2] * w;
a[j] = (u + t) % MOD;
a[j + h / 2] = (u - t + 1LL * MOD * MOD) % MOD;
w = mul(w,wn);
}
}
}
if(on == -1) {
int invL = fpow(LEN,MOD - 2);
for(int i = 0 ; i < LEN ; ++i) a[i] = mul(a[i],invL);
}
}
void Solve() {
read(N);
int u,v;
for(int i = 1 ; i < N ; ++i) {
read(u);read(v);add(u,v);add(v,u);
}
dfs(1,0);
fac[0] = 1;
for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);
invfac[N] = fpow(fac[N],MOD - 2);
for(int i = N - 1 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
for(int i = 0 ; i <= N ; ++i) f[N - i] = invfac[i];
for(int i = 1 ; i <= N ; ++i) b[i] = mul(b[i],fac[i]);
W[0] = 1;W[1] = fpow(G,(MOD - 1) / L);
for(int i = 2 ; i < L ; ++i) W[i] = mul(W[i - 1],W[1]);
int t = 1;
while(t <= 2 * N) t <<= 1;
NTT(b,t,1);NTT(f,t,1);
for(int i = 0 ; i < t ; ++i) f[i] = mul(f[i],b[i]);
NTT(f,t,-1);
for(int i = 1 ; i <= N ; ++i) {
int ans = mul(f[i + N],invfac[i]);
ans = inc(mul(N,C(N,i)),MOD - ans);
out(ans);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
最新文章
- windows bat 批处理 !vm 合并快播文件
- 判断 0 和 &#39;&#39; 以及 empty null false的关系
- jquery弹出关闭遮罩层实例
- n &; (n-1)
- 让asp.net web api同时支持[AcceptVerbs(";GET";,";POST";)]
- SDK文件夹下内容介绍
- python 3.5 之 单双三引号
- OS X 10.10 Yosemite Beta能够下载了
- 用开源软件建垂直搜索引擎 转载 http://news.cnblogs.com/n/60041/
- AutoMapper5.0创建对象方法更新
- maven用框架编写网页运行出现HTTP Status 500 - Unable to compile class for JSP
- 揭开Docker的神秘面纱
- Java知多少(2)虚拟机(JVM)以及跨平台原理
- vue-router路由管理器
- 【UI测试】--菜单位置
- 如何永久激活(破解) IntelliJ IDEA 2018.1.3
- SAP+ 差旅报销集成方案的实现
- angularjs 本地数据存储LocalStorage
- python模拟随机游走
- C语言 &#183; 运用结构体的排序方法
热门文章
- Autolayout下使用代码改变frame无效
- 新建springboot项目启动出错 Failed to configure a DataSource: &#39;url&#39; attribute is not specified and no embedded datasource could be configured.
- iOS二维码扫描的实现(Swift)
- [整理]标准C中的";布尔";类型
- 【转】 jquery easyui datagrid使用,分页、排序、查询
- extern函数声明(转)
- Mysql服务优化
- css_清除浮动的4种方式
- Mysql中truncate table和delete语句的区别
- 如何扎实自己的Java基础?