vps打开网站很慢,江苏建发建设项目咨询有限公司网站,扬州seo招聘,东莞网站建设 石佳正题
题目链接:https://www.luogu.com.cn/problem/P5825 题目大意
对于每个kkk#xff0c;求有多少个长度为nnn的排列有kkk个位置上升。 1≤n≤21051\leq n\leq 2\times 10^51≤n≤2105 解题思路
考虑到同时考虑大于和小于十分麻烦#xff0c;设fif_ifi表示钦定iii个上升…正题
题目链接:https://www.luogu.com.cn/problem/P5825 题目大意
对于每个kkk求有多少个长度为nnn的排列有kkk个位置上升。 1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105 解题思路
考虑到同时考虑大于和小于十分麻烦设fif_ifi表示钦定iii个上升时的方案
连续的上升段可以视为同一个组那么整个序列就会被分为mn−kmn-kmn−k段每个组内都是无序的。
所以可以考虑一下EGF\text{EGF}EGF来做因为不能选空段那么每一段的生成函数就是ex−1e^x-1ex−1。
也就是fn−m(ex−1)m[xn]f_{n-m}(e^x-1)^m[x^n]fn−m(ex−1)m[xn]。二项式定理展开一下 fm∑i0m(mi)(−1)m−ieixf_m\sum_{i0}^m\binom{m}{i}(-1)^{m-i}e^{ix}fmi0∑m(im)(−1)m−ieix ∑i0mm!i!(m−i)!(−1)m−iinn!\sum_{i0}^m\frac{m!}{i!(m-i)!}(-1)^{m-i}\frac{i^n}{n!}i0∑mi!(m−i)!m!(−1)m−in!in m!n!∑i0m(−1)m−i(m−i)!ini!\frac{m!}{n!}\sum_{i0}^m\frac{(-1)^{m-i}}{(m-i)!}\frac{i^n}{i!}n!m!i0∑m(m−i)!(−1)m−ii!in NTT\text{NTT}NTT卷起来就好了。
然后gig_igi表示恰好有iii个的话上二项式反演即可 fi∑j0i(ij)gj⇒gi∑ji(−1)j−i(ji)fjf_i\sum_{j0}^i\binom{i}{j}g_j\Rightarrow g_i\sum_{ji}(-1)^{j-i}\binom{j}{i}f_jfij0∑i(ji)gj⇒giji∑(−1)j−i(ij)fj 这个也是显然可以卷积快速求得的。
顺带一提的是这个求得其实就是欧拉数⟨nk⟩\left\langle\begin{matrix} n\\k\end{matrix}\right\rangle⟨nk⟩
联立上面的fif_ifi和gig_igi的式子可以得到欧拉数的通式 ⟨nk⟩∑i0n−k(−1)n−k−iin(n1kj1)\left\langle\begin{matrix} n\\k\end{matrix}\right\rangle\sum_{i0}^{n-k}(-1)^{n-k-i}i^n\binom{n1}{kj1}⟨nk⟩i0∑n−k(−1)n−k−iin(kj1n1)
这个可以一次卷积求得
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N8e510,P998244353;
ll n,m,inv[N],fac[N],f[N],g[N],r[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void NTT(ll *f,ll op){for(ll i0;im;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pm;p1){ll tmppower(3,(P-1)/p),len(p1);if(op-1)tmppower(tmp,P-2);for(ll k0;km;kp){ll buf1;for(ll ik;iklen;i){ll ttf[ilen]*buf%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(m,P-2);for(ll i0;im;i)f[i]f[i]*invn%P;}return;
}
signed main()
{scanf(%lld,n);inv[1]1;for(ll i2;in;i)inv[i]P-inv[P%i]*(P/i)%P;inv[0]fac[0]1;for(ll i1;in;i)inv[i]inv[i-1]*inv[i]%P,fac[i]fac[i-1]*i%P;for(ll i0;in;i)f[i]inv[i]*power(i,n)%P,g[i](i1)?(P-inv[i]):inv[i];m1;while(m2*n)m1;for(ll i0;im;i)r[i](r[i1]1)|((i1)?(m1):0);NTT(f,1);NTT(g,1);for(ll i0;im;i)f[i]f[i]*g[i]%P;NTT(f,-1);memset(g,0,sizeof(g));for(ll i0;im;i)f[i](in)?(f[i1]*fac[i1]%P):0;for(ll in;im;i)f[i]0;for(ll i0;in;i){f[i]f[i]*fac[n-i-1];f[i](i1)?(P-f[i]):f[i];g[i]inv[i];}NTT(f,1);NTT(g,1);for(ll i0;im;i)f[i]f[i]*g[i]%P;NTT(f,-1);for(ll i0;in-i-1;i)swap(f[i],f[n-i-1]);for(ll i0;in;i){f[i]f[i]*inv[i]%P;f[i]((n-i)1)?f[i]:(P-f[i]);printf(%lld ,f[i]%P);}putchar(0);return 0;
}
