博客
关于我
[bzoj5093][第二类斯特林数][NTT]图的价值
阅读量:86 次
发布时间:2019-02-26

本文共 2338 字,大约阅读时间需要 7 分钟。

Description

“简单无向图”是指无重边、无自环的无向图(不一定连通)。 一个带标号的图的价值定义为每个点度数的k次方的和。

给定n和k,请计算所有n个点的带标号的简单无向图的价值之和。 因为答案很大,请对998244353取模输出。

Input

第一行包含两个正整数n,k(1<=n<=10^9,1<=k<=200000)。

Output

输出一行一个整数,即答案对998244353取模的结果。

Sample Input

6 5

Sample Output

67584000

题解

一般都要单独考虑一个点的贡献

显然这个点的贡献是独立的,最后乘一个n就可以
那单独一个点的贡献就是
∑ i = 1 n − 1 C n − 1 i ∗ 2 ( n − 1 ) ( n − 2 ) 2 ∗ i k \sum_{i=1}^{n-1}C_{n-1}^i*2^{\frac{(n-1)(n-2)}{2}}*i^k i=1n1Cn1i22(n1)(n2)ik
2的次幂是常数,提到前面去,把n减一,显然我们只需要算
∑ i = 1 n C n i ∗ i k \sum_{i=1}^nC_{n}^{i}*i^k i=1nCniik
根据第二类斯特林数的性质,我们可以知道
∑ i = 1 n C n i ∑ j = 0 m i n ( i , k ) S ( k , j ) ∗ j ! ∗ C i j \sum_{i=1}^nC_{n}^{i}\sum_{j=0}^{min(i,k)}S(k,j)*j!*C_{i}^{j} i=1nCnij=0min(i,k)S(k,j)j!Cij
乘法分配律一下,显然可以把斯特林数提前
∑ i = 0 m i n ( n , k ) S ( k , i ) ∗ i ! ∗ ∑ j = i n C n j ∗ C j i \sum_{i=0}^{min(n,k)}S(k,i)*i!*\sum_{j=i}^{n}C_n^j*C_{j}^{i} i=0min(n,k)S(k,i)i!j=inCnjCji
后面的式子的意义就是在n中选i个数,其它可选可不选,所以就是
∑ i = 0 m i n ( n , k ) S ( k , i ) ∗ i ! ∗ C n i ∗ 2 n − i \sum_{i=0}^{min(n,k)}S(k,i)*i!*C_{n}^{i}*2^{n-i} i=0min(n,k)S(k,i)i!Cni2ni
现在就是要算前面的斯特林数了
可以容斥然后NTT n l o g n nlogn nlogn求,点一下就知道啦

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long#define mp(x,y) make_pair(x,y)#define pll pair
#define pii pair
using namespace std;inline LL read(){ LL f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f;}int stack[20];inline void write(int x){ if(x<0){ putchar('-');x=-x;} if(!x){ putchar('0');return;} int top=0; while(x)stack[++top]=x%10,x/=10; while(top)putchar(stack[top--]+'0');}inline void pr1(int x){ write(x);putchar(' ');}inline void pr2(int x){ write(x);putchar('\n');}const LL mod=998244353;const int MAXN=200005;LL pow_mod(LL a,LL b){ LL ret=1; while(b) { if(b&1)ret=ret*a%mod; a=a*a%mod;b>>=1; } return ret;}LL A[MAXN*4],B[MAXN*4];int R[MAXN*4],L;void NTT(LL *y,int len,int on){ for(int i=0;i
=0;i--)inv[i]=inv[i+1]*(i+1)%mod; n=read();K=read();n--; init(); int ln; for(ln=1;ln<=2*K;ln<<=1)L++; for(int i=0;i
>1]>>1)|(i&1)<<(L-1); int temp=-1; for(int i=0;i<=K;i++) { temp*=-1; A[i]=temp*inv[i]%mod; LL u1=pow_mod(i,K),u2=inv[i]; B[i]=u1*u2%mod; } NTT(A,ln,1);NTT(B,ln,1); for(int i=0;i

转载地址:http://immu.baihongyu.com/

你可能感兴趣的文章
Mysql 数据类型一日期
查看>>
MySQL 数据类型和属性
查看>>
mysql 敲错命令 想取消怎么办?
查看>>
Mysql 整形列的字节与存储范围
查看>>
mysql 断电数据损坏,无法启动
查看>>
MySQL 日期时间类型的选择
查看>>
Mysql 时间操作(当天,昨天,7天,30天,半年,全年,季度)
查看>>
MySQL 是如何加锁的?
查看>>
MySQL 是怎样运行的 - InnoDB数据页结构
查看>>
mysql 更新子表_mysql 在update中实现子查询的方式
查看>>
MySQL 有什么优点?
查看>>
mysql 权限整理记录
查看>>
mysql 权限登录问题:ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)
查看>>
MYSQL 查看最大连接数和修改最大连接数
查看>>
MySQL 查看有哪些表
查看>>
mysql 查看锁_阿里/美团/字节面试官必问的Mysql锁机制,你真的明白吗
查看>>
MySql 查询以逗号分隔的字符串的方法(正则)
查看>>
MySQL 查询优化:提速查询效率的13大秘籍(避免使用SELECT 、分页查询的优化、合理使用连接、子查询的优化)(上)
查看>>
mysql 查询数据库所有表的字段信息
查看>>
【Java基础】什么是面向对象?
查看>>