是个水题?
重点是得发现一个结论:若排列 a 不合法,则一定存在 1≤i<n,满足 a1…i 是 1…i 的一个排列。
则此时 i+1 是第一个使得序列不完美的位置。
设 fn 表示 n 的答案,则取补集得 fn=n!−n−1∑i=1fi(n−i)!
移项并令 f0=0 得 n∑i=0fi(n−i)!+[n=0]=n!
设 F(x)=∞∑i=0fixi,G(x)=∞∑i=0i!xi,则根据上式有 F(x)G(x)+1=G(x)(1−F(x))G(x)=1F(x)=1−1G(x)
多项式求逆即可。
代码:
1 |
|