BZOJ 3684: 大朋友和多叉树 [拉格朗日反演 多项式k次幂 生成函数]
2024-09-02 21:47:45
3684: 大朋友和多叉树
题意:
求有n个叶子结点,非叶节点的孩子数量\(\in S, a \notin S\)的有根树个数,无标号,孩子有序。
鏼鏼鏼!
树的OGF:\(T(x) = \sum_{i\ge 0} t_ix^i\)
\[T(x) = x + \sum_{k \in S}T(x)^k
\]
\]
因为一个树是叶子结点或者其他树拼接成的“序列”
\[x = T(x) -\sum_{k \in S}T(x)^k = G(T(x))
\]
\]
所以\(T(x)\)是\(G(x) = x - \sum_{k \in S}x^k\)的复合逆,直接上拉格朗日反演求第n项的值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = (1<<18) + 5;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int P = 950009857;
inline int Pow(ll a, int b) {
ll ans = 1;
for(; b; b>>=1, a=a*a%P)
if(b&1) ans=ans*a%P;
return ans;
}
ll inv[N];
namespace ntt {
int g = 7, rev[N];
void dft(int *a, int n, int flag) {
int k = 0; while((1<<k) < n) k++;
for(int i=0; i<n; i++) {
rev[i] = (rev[i>>1]>>1) | ((i&1)<<(k-1));
if(i < rev[i]) swap(a[i], a[rev[i]]);
}
for(int l=2; l<=n; l<<=1) {
int m = l>>1, wn = Pow(g, flag == 1 ? (P-1)/l : P-1-(P-1)/l);
for(int *p = a; p != a+n; p += l)
for(int k=0, w=1; k<m; k++, w = (ll)w*wn %P) {
int t = (ll) w * p[k+m] %P, r = p[k];
p[k+m] = (r - t + P) %P;
p[k] = (r + t) %P;
}
}
if(flag == -1) {
ll inv = Pow(n, P-2);
for(int i=0; i<n; i++) a[i] = a[i] * inv %P;
}
}
void inverse(int *a, int *b, int l) {
static int t[N];
if(l == 1) {b[0] = Pow(a[0], P-2); return;}
inverse(a, b, l>>1);
int n = l<<1;
for(int i=0; i<l; i++) t[i] = a[i], t[i+l] = 0;
dft(t, n, 1); dft(b, n, 1);
for(int i=0; i<n; i++) b[i] = (ll) b[i] * (2 - (ll) t[i] * b[i] %P + P) %P;
dft(b, n, -1); for(int i=l; i<n; i++) b[i] = 0;
}
void ln(int *a, int *b, int l) {
static int da[N], ia[N];
int n = l<<1;
for(int i=0; i<n; i++) da[i] = ia[i] = 0;
for(int i=0; i<l-1; i++) da[i] = (ll) (i+1) * a[i+1] %P;
inverse(a, ia, l);
dft(da, n, 1); dft(ia, n, 1);
for(int i=0; i<n; i++) b[i] = (ll) da[i] * ia[i] %P;
dft(b, n, -1);
for(int i=l-1; i>0; i--) b[i] = (ll) inv[i] * b[i-1] %P; b[0] = 0;
for(int i=l; i<n; i++) b[i] = 0;
}
void exp(int *a, int *b, int l) {
static int t[N];
if(l == 1) {b[0] = 1; return;}
exp(a, b, l>>1);
int n = l<<1;
for(int i=0; i<n; i++) t[i] = 0;
ln(b, t, l);
for(int i=0; i<l; i++) t[i] = (a[i] - t[i] + P) %P; t[0] = (t[0] + 1) %P;
dft(b, n, 1); dft(t, n, 1);
for(int i=0; i<n; i++) b[i] = (ll) b[i] * t[i] %P;
dft(b, n, -1); for(int i=l; i<n; i++) b[i] = 0;
}
void power(int *a, int k, int l) {
static int t[N];
int n = l<<1;
for(int i=0; i<n; i++) t[i] = 0;
ln(a, t, l);
for(int i=0; i<l; i++) t[i] = (ll) k * t[i] %P;
for(int i=0; i<n; i++) a[i] = 0;
exp(t, a, l);
}
}
int n, m, g[N], a[N];
int main() {
//freopen("in", "r", stdin);
n=read(); m=read();
g[0] = 1;
for(int i=1; i<=m; i++) g[read()-1] = P-1;
int len = 1; while(len <= n) len <<= 1;
inv[1] = 1;
for(int i=2; i < len<<1; i++) inv[i] = (P - P/i) * inv[P%i] %P;
ntt::inverse(g, a, len);
ntt::power(a, n, len);
int ans = (ll) a[n-1] * inv[n] %P;
printf("%d", ans);
}
最新文章
- BZOJ 1176: [Balkan2007]Mokia
- MySQL用户与权限管理
- 渴切-开源中文css框架
- 疯狂java讲义——初始化块
- 非常好的在网页中显示pdf的方法
- Android四大组件之一:Service(服务)
- hdu 2894
- EntityFramework 基础提供程序在 Open 上失败。
- css 权威指南笔记(三)结合css和XHTML
- Android SDK Manager安装报错
- JsonResult,Controller.Json
- HTTP协议报文结构及示例
- js vue 在页面中将摄像头放在一个标签里展示,(模仿手机拍照功能)
- Maven多项目继承:dependencyManagement scope=import
- android 使用Canvas画箭头
- spring mvc 映射与适配器
- python 获取列表中次大的数值.
- wordpress 解决文章内http链接问题
- [LeetCode解题报告] 502. IPO
- gdb 脚本调试