牛客练习赛32 F Friendly Polynomial

Description

求 $i \in [1,n-1], a_1,a_2,…,a_i $ 构成一个 $i$ 排列的个数
$T$ 次询问
$n,T \leqslant 10^5$

Solution

老年人
体谅一下
没有完整的代码
只有 $O(n^2)$ 的做法
其实就是我不会写NTT了

感觉
这题
没啥难度

除了
NTT
多项式求逆

还有
我的脑子

阻碍了我做出这道题

留坑。
以后如果想起来就填好吧。

先说一下心路历程好吧。

先想暴力。
然后我发现了好多检查前缀是否是i排列的方法。
取最大值，求和 貌似都可以

然后看一下有啥性质

• 最大的在第一个一定合法，在最后一个一定不合法

一开始我考虑的是递推，从$n-1$递推到$n$，我觉得最大的影响就是最后一个数字的位置，分成两个记录，分为被之前影响的和未被影响的。
然后我去洗澡了233
然后发现有问题，其实这个题很简单就是分为两个合法和不合法就行了，之前想的未被影响的其实就是合法的
然后可以从前往后来做，考虑贡献，一个不合法的只能贡献一次，对于$i$位合法的才能对后面产生贡献
枚举第一个不合法的点，然后后面直接排列就行了。

公式

$$\begin{align*}f[n]&=\sum_{i=1}^{n-1} ((n-i)!\times (i!-f[i]))\\&=(\sum_{i=1}^{n-1}(n-i)!\times i!)-(\sum_{i-1}^{n-1}(n-1)!\times f[i])\end{align*}$$

多项式

$$f=g^2-g\times f\Rightarrow f=\frac{g^2}{1+g}$$

好了，双手一撒。
掰掰了您内！

Code

$ O(n^2) $

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const int N = 1005;
ll p = 998244353;

ll f[N]; // 0 - illegal / 1 legal
ll pn[N];

ll pw(ll a, ll b, ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }

ll C(ll n, ll m) { 
    if(n<m) return 0;
    return pn[n]*pw(pn[m],p-2)%p*pw(pn[n-m],p-2)%p;
}
void init() {
    f[1]=0;
    pn[0]=pn[1]=1;
    for(int i=2;i<N;i++) pn[i]=pn[i-1]*i%p;
}

void work() {
    for(int i=2;i<N;i++) {
        for(int j=1;j<i;j++) f[i]=(f[i]+(pn[j]-f[j]+p)%p*pn[i-j]%p)%p;
    }
}

int main() {
    init();
    work();
    int n;
    cin >> n;
    cout << f[n] << endl;
    return 0;
}