博客
关于我
[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 - ERROR 1406
查看>>
mysql - 视图
查看>>
MySQL - 解读MySQL事务与锁机制
查看>>
MTTR、MTBF、MTTF的大白话理解
查看>>
mt_rand
查看>>
mysql -存储过程
查看>>
mysql /*! 50100 ... */ 条件编译
查看>>
mudbox卸载/完美解决安装失败/如何彻底卸载清除干净mudbox各种残留注册表和文件的方法...
查看>>
mysql 1264_关于mysql 出现 1264 Out of range value for column 错误的解决办法
查看>>
mysql 1593_Linux高可用(HA)之MySQL主从复制中出现1593错误码的低级错误
查看>>
mysql 5.6 修改端口_mysql5.6.24怎么修改端口号
查看>>
MySQL 8.0 恢复孤立文件每表ibd文件
查看>>
MySQL 8.0开始Group by不再排序
查看>>
mysql ansi nulls_SET ANSI_NULLS ON SET QUOTED_IDENTIFIER ON 什么意思
查看>>
multi swiper bug solution
查看>>
MySQL Binlog 日志监听与 Spring 集成实战
查看>>
MySQL binlog三种模式
查看>>
multi-angle cosine and sines
查看>>
Mysql Can't connect to MySQL server
查看>>
mysql case when 乱码_Mysql CASE WHEN 用法
查看>>