bzoj 4555 题目解答:这道题解决的关键是知道第二类斯特林数的通项公式。
然后就可以用一遍 NTT 求解了
代码
- #include#include#include#include#include#define N 500003#define LL long long#define p 998244353using namespace std;
- LL f[N],
- g[N],
- inv[N],
- jc[N],
- mi[N];
- int n,
- n1,
- L,
- R[N];
- LL quickpow(LL num, LL x) {
- LL base = (num % p p) % p;
- LL ans = 1;
- while (x) {
- if (x & 1) ans = ans * base % p;
- x >>= 1;
- base = base * base % p;
- }
- return ans;
- }
- void NTT(LL a[N], int n, int opt) {
- for (int i = 0; i > 1] >> 1) | ((i & 1) << (L - 1));
- NTT(f, n1, 1);
- NTT(g, n1, 1);
- for (int i = 0; i <= n1; i++) f[i] = f[i] * g[i] % p;
- NTT(f, n1, -1);
- LL t = quickpow(n1, p - 2);
- for (int i = 0; i <= n1; i++) f[i] = f[i] * t % p;
- LL ans = 0;
- for (int i = 0; i <= n; i++) ans = (ans + f[i] * jc[i] % p * mi[i] % p) % p;
- printf("%lld\n", (ans % p p) % p);
- }
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-17/20564264.html