CF1089I Interval-Free Permutations

题目大意：

有一个排列，长度为n，一个区间为连续段当且仅当最大值减最小值加一为区间的长度。问所有长度为n的排列，有多少个满足只有长度为1或n的连续段。要求n^3求出所有长度为1到n的答案。

思考：
考虑连续段的性质。容易发现的是，两个相交连续段的并还是一个连续段。

首先我们特判n=2。然后我们i使用容斥，考虑所有不应该被算到答案里的排列，那么可以通过以下算法把它们划分为两类：

1.从当前左端点找到最右的且不能为n（注意这个下标是原序列的下标）的右端点R，使得[左端点，R]为连续段。

2.从当前右端点找到最左的且不能为1的左端点L，使得[L，右端点]为连续段。

3.计数器cnt加一。

4.若两区间的并覆盖了未覆盖的区间，结束过程；否则将区间[1,R],[L,n]覆盖，左端点变为R+1，右端点变为L-1，重复上述过程。

我们首先知道，这个算法一定会结束。于是我们根据cnt分类：若cnt=1，则将该排列分到第1类，否则分到第2类。可以发现，这样是良定义的，即第一类中划分出的区间一定是极大的，并且它们的并为整个排列。第2类中划分出的区间一定是极大且互不相交的：因为一旦出现了一个更大的能包含它们的区间，它在上述算法中一定会被选到（根据相交连续段的并还是连续段的性质）。

因此，我们考虑计算这两类中的贡献。

对于第1类，我们首先知道要么是左边的连续段，要么是右边的连续段，它包含数字1。我们假设1在左边，并枚举左边的连续段的右端点i，那么答案会减去$2*sum_{i=1}^{n-1}{I(n-i)*i!}$，其中$I(n)$表示所有1~n-1的前缀均不构成包含1的连续段的排列个数（注意I(n-i)，这个写法有助于理解）。正确性在于我们钦定右边n-i个位置不管怎么选都无法构成长度大于i的且包含1的连续段，而左边的数字为1~i,因此[1,i]这个区间一定是连续段，从而左边的连续段第一次出现的右端点一定为i。而显然右边的区间的左端点小于等于i。这样算出来的一定是所有的第1类贡献。

$I(n)$的计算：$I(n)=n!-sum_{i=1}^{n-1}{I(i)*(n-i)!}$，理由是容斥，枚举小于n且第一次出现包含1的连续段[1,i]，剩下显然随便填。

对于第2类，它的结构与我们需要计算的答案高度地类似。我们知道，第2类中的所有方案的区间数一定大于等于3，考虑一个方案的区间划分[l1,r1],[l2,r2],...,[lk,rk]，如果我们知道了它们的偏序关系（即一个区间要么最大值小于另一个区间的最小值，要么最小值大于另一个区间的最大值），那我们就能将数字1~n唯一地划分到这些区间中。而这样本质不同的偏序关系恰好有$ans(k)$个！其中$ans(n)$是我们最后要求的答案。于是我们只需要计算$prod{(r_i-l_i+1)!}$的和即可。这部分是三次方的。

于是，我们就有答案$ans(n)=n!-2*sum_{i=1}^{n-1}{I(i)*(n-i)!}-sum_{i=3}^{n-1}{B(n,i)*ans_i}$，其中$B(n,i)$为上面那个乘积的和。注意后面的减法下界是3，上界是n-1（因为至少要有一段长度大于等于2）。

最后记得特判n=2，因为它并不在上述讨论中。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int lim=400;
int n;
ll f[405],g[405][405],ans[405],fac[405];
ll mod;
inline void add(ll&x,ll y)
{
    x=(x+y)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T>>mod;
    fac[0]=1;
    for(int i=1;i<=lim;++i)
        fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=lim;++i)
    {
        f[i]=fac[i];
        for(int j=1;j<=i-1;++j)
            add(f[i],-f[j]*fac[i-j]);
    }
    g[0][0]=1;
    for(int i=1;i<=lim;++i)
        for(int j=1;j<=i;++j)
            for(int t=1;t<=i;++t)
                add(g[i][j],g[i-t][j-1]*fac[t]);
    for(int i=1;i<=lim;++i)
    {
        ans[i]=fac[i];
        for(int j=1;j<=i-1;++j)
            add(ans[i],-f[j]*fac[i-j]*2);
        for(int j=3;j<=i-1;++j)
            add(ans[i],-g[i][j]*ans[j]);
    }
    ans[2]=2;// !!!!!!! 
    while(T--)
    {
        int x;
        cin>>x;
        cout<<(ans[x]%mod+mod)%mod<<endl;
    }
    return 0;
}