CF932E Team Work
CF932E Team Work
讲道理不难，但是我推不出来（指在模数为998244353的情况下的 \(O(k)\) 做法）我只能搞出 \(O (K \log N)\) 的，但是需要模数为998244353（你要用FFT也行，不保证精度）。
那么考虑 \(O(K^2)\)。显然，你只需要 这题 就行了。 （推导过程容易发现 \(j \gt k\) 和 \(j=0\) 时，值为0。
\[\sum_{i=1}^n \binom n i i^k \\ = \sum_{i=1}^n \binom n i \sum_{j=0}^i {k\brace j}j! \binom i j \\ = \sum_{j=1}^k {k \brace j} j! \sum_{i=j}^n \binom n i \binom i j\\ = \sum_{j=1}^k {k \brace j} j! \sum_{i=j}^n \binom n j \binom {n-j} {i-j} \\ = \sum_{j=1}^k {k \brace j} j! \binom n j \sum_{i=j}^n \binom {n-j} {i-j} \\ = \sum_{j=1}^k {k \brace j} j! \binom n j 2^{n-j} \]这题就可以 \(O(K^2)\) 完成了。但是我们怎么可以放弃（大雾），我们已知
\[{n \brace k}\\ = \frac{1}{k!} \sum_{i=0}^k (-1)^i \binom ki (k-i)^n \\ = \sum_{i=0}^k \frac{(-1)^i}{i!} \frac {(k-i)^n} {(k-i)!} \]那么我们可以直接卷一下就变成 \(O (K \log N)\) 了（模数998244353）。
\(O(K)\) 做法请去看min_25博客。
/*
Name:
Author: Gensokyo_Alice
Date:
Description:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include