洛谷·[HEOI2016/TJOI2016]求和【including 第二类斯特林数
程序员文章站
2022-04-20 22:19:23
...
初见安~这里是传送门:洛谷P4091 求和
题解
这是本狸做的第二个比较【硬核】干货的黑题……所以卡了好久……
说白了就是推公式,然后套NTT完事儿。【啪
首先我们要知道:关于第二类斯特林数是个什么东西。
将n个有区别的小球放入m个无区别的盒子里并保证每个盒子都不为空,方案数就是S(n, m)。
假设m个盒子有区别,并有性质表示第i个盒子为空,那么我们要求的就是。
所以根据容斥定理,容斥一下就好了:
所以s的展开式已经得到了,那么公式怎么推呢———【前方高能】
【公式都是在markdown里手打的,这里的公式编辑器用着不舒服QuQ】
为了简便【少打几个sum】,我们设,则。
前面那两个都是可以预处理算的,所以我们接下来处理g。
看后面那一个求和部分——这不就是等比数列求和嘛!!!所以再收:
所以现在,出现的变量就只有k和j了。隐隐有点卷积的味道了呢,那我们就尝试构造一下:
【糟糕,最后这里写错了,是不是 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——