2.8

· · 休闲·娱乐

A. Gym102956B Beautiful Sequence Unraveling

注意到 m 很大，而判定 a_i 具体的值毫不相关，先考虑如何给 a 离散化。

注意到直接钦定有多少个值这件事情是困难的，但是至多比较容易，我们定义 A_i 为钦定出现 i 个值的方案数，B_i 为出现至多 i 个值的方案数，那么有：

A_i=B_i-\sum\limits_{j=1}^{i-1}{i \choose j}A_j ans=\sum\limits_{i=1}^m{m \choose i} A_i

现在我们把问题转化为求 B，容易想到定义 f_{i,j} 表示长度为 i 的序列，里面的至多 j 个值的合法序列方案数。

考虑容斥，枚举最后一个不合法的位置 k，以及 \max=\min 的值 t，那么有：

因此有：

f_{i,j}\gets j^i-\sum\limits_{k=1}^{i-1}\sum\limits_{t=1}^{j}(t^k-(t-1)^k)(f_{i-k,j-t+1}-f_{i-k,j-t})

乍一看这个是 O(n^4) 的，我们考虑把括号拆开，以第一项为例，即 t^kf_{i-k,j-t+1}，这是卷积的形式，但是模数不是 NTT 模数！

注意到其实幂的乘除可以转化为指数的加减，因此把式子转化为：t^kf_{i-k,j-t+1}=\dfrac{t^i}{t^{i-k}}f_{i-k,j-t+1}，然后用前缀和处理即可。

时间复杂度 O(n^3)，不知道我为啥这么慢。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405;
int n,k,p,f[N][N],g[N],h[N][N][N],pw[N][N],ipw[N][N],b[N],a[N];
int qpow(int a,int b){
    int s=1;
    while(b){
        if(b&1) s=s*a%p;
        a=a*a%p,b>>=1;
    }
    return s;
}
int C(int n,int m){
    return !m?1:C(n-1,m-1)*n%p*qpow(m,p-2)%p;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k>>p;
    for(int i=1;i<=min(n,k);++i){
        ipw[i][0]=pw[i][0]=1;
        for(int j=1;j<=n;++j) ipw[i][j]=qpow(pw[i][j]=pw[i][j-1]*i%p,p-2);
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=min(n,k);++j){
        for(int t=1;t<=j;++t) f[i][j]=((f[i][j]+pw[t][i]*h[i-1][j-t+1][t]-pw[t][i]*h[i-1][j-t][t]%p-pw[t-1][i]*h[i-1][j-t+1][t-1]+pw[t-1][i]*h[i-1][j-t][t-1])%p+p)%p;
        f[i][j]=(pw[j][i]-f[i][j]+p)%p;
        for(int t=1;t<=min(n,k);++t) h[i][j][t]=(h[i-1][j][t]+f[i][j]*ipw[t][i])%p;
    }
    for(int i=1;i<=min(n,k);++i) b[i]=f[n][i];
    for(int i=1;i<=min(n,k);++i){
        a[i]=b[i];
        for(int j=1;j<i;++j) a[i]=(a[i]-C(i,j)*a[j]%p+p)%p;
    }
    int ans=0;
    for(int i=1;i<=min(n,k);++i) ans=(ans+C(k,i)*a[i])%p;
    cout<<ans<<endl;
    return 0;
}