欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

程序员文章站 2022-04-20 22:19:23
...

初见安~这里是传送门:洛谷P4091 求和

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

题解

这是本狸做的第二个比较【硬核】干货的黑题……所以卡了好久……

说白了就是推公式,然后套NTT完事儿。【啪

首先我们要知道:关于第二类斯特林数是个什么东西。

将n个有区别的小球放入m个无区别的盒子里并保证每个盒子都不为空,方案数就是S(n, m)。

假设m个盒子有区别,并有性质洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数表示第i个盒子为空,那么我们要求的就是洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

所以根据容斥定理,容斥一下就好了:

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

所以s的展开式已经得到了,那么公式怎么推呢———【前方高能】

【公式都是在markdown里手打的,这里的公式编辑器用着不舒服QuQ】

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

为了简便【少打几个sum】,我们设洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数,则洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

前面那两个都是可以预处理洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数算的,所以我们接下来处理g。

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

看后面那一个求和部分——这不就是等比数列求和嘛!!!所以再收:

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数

所以现在,出现的变量就只有k和j了。隐隐有点卷积的味道了呢,那我们就尝试构造一下:

洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数【糟糕,最后这里写错了,是洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数不是洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数 QuQ

所以最后函数g就是一个卷积了!!!我们把g NTT求一下,再带入f里面On求值,这个题就结束啦!!!

(从来没写过这么多公式……好累)

上代码啦——

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define int long long
#define maxn 300005
using namespace std;
typedef long long ll;
const int mod = 998244353, mx = 200005;
int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}

int r[maxn], l = 0, len = 1;//这一部分都是NTT操作
ll pw(ll a, ll b) {ll ans = 1; while(b) {if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1;} return ans;}
void NTT(ll *c, int flag) {
	for(int i = 1; i < len; i++) if(i < r[i]) swap(c[i], c[r[i]]);
	for(int mid = 1; mid < len; mid <<= 1) {
		ll gn = pw(3, (mod - 1) / (mid << 1));
		if(flag == -1) gn = pw(gn, mod - 2);
		for(int L = mid << 1, ls = 0; ls < len; ls += L) {
			ll g = 1;
			for(int k = 0; k < mid; k++, g = g * gn % mod) {
				ll tmp = g * c[ls + k + mid] % mod;
				c[ls + k + mid] = (c[ls + k] - tmp + mod) % mod;//注意顺序!!!!!!! 
				c[ls + k] = (c[ls + k] + tmp) % mod;
			}
		}
	}
}

int n;
ll a[maxn], b[maxn], inv[maxn], fac[maxn], rev[maxn], pr[maxn], ans = 0;
signed main() {
	n = read();
	while(len <= n + n) len <<= 1, l++;//NTT
	for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
	
	fac[0] = inv[0] = rev[1] = pr[0] = 1;//rev是单个值的逆元,pr是2的幂次,这一部分都是在预处理
	for(int i = 1; i <= mx; i++) fac[i] = fac[i - 1] * i % mod;
	inv[mx] = pw(fac[mx], mod - 2);
	for(int i = mx - 1; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
	for(int i = 2; i <= mx; i++) rev[i] = (mod - mod / i) * rev[mod % i] % mod;;
	for(int i = 1; i <= mx; i++) pr[i] = pr[i - 1] * 2 % mod;
	
	for(int i = 0, kd = 1; i <= n; i++, kd = -kd) a[i] = kd * inv[i];//处理公式中a和b的值
	b[0] = 1, b[1] = n + 1;
	for(int i = 2; i <= n; i++) b[i] = (pw(i, n + 1) - 1 + mod) % mod * inv[i] % mod * rev[i - 1] % mod;

	NTT(a, 1); NTT(b, 1);//开始NTT
	for(int i = 0; i <= len; i++) a[i] = a[i] * b[i] % mod;
	NTT(a, -1);
	for(int i = 0; i <= len; i++) a[i] = a[i] * pw(len, mod - 2) % mod;
	
	for(int i = 0; i <= n; i++) ans = (ans + pr[i] * fac[i] % mod * a[i] % mod) % mod;
	printf("%lld\n", ans);
	return 0;
}

迎评:)
——End——