CF1603E A Perfect Problem

· · 题解

注：完美为 perfect，好的为 good。好的序列为 \min\times\max\ge\sum 的序列，完美的序列为每个子序列都好的序列。

首先，我们考虑排好序的完美序列，任意完美的序列的任意排列都是完美的。

然后我们发现：

定理 1 一个排好序的序列是完美的当且仅当其每个子区间都是好的。

证明：枚举每个 i 和 j，我们发现 \min\times\max=a_i\times a_j 固定 \sum 最大时即为选择整个子区间 [i,j] 时。

定理 2 一个排好序的序列是完美的当且仅当其每个前缀都是好的。

证明：此时，a_ia_j\ge a_1a_j\ge \sum\limits_{k=1}^j a_j\ge \sum\limits_{k=i}^j a_j，则有每个前缀是好的可以推出每个子区间是好的。

定理 3 \forall k,a_k\ge k。

证明：若 a_k<k，\sum\limits_{i=1}^ka_i\ge ka_1>a_1a_k，违反定理 2。

定理 4 若 a_k=k，则 \forall i\le k,a_i=k。

证明：由定理 2 a_1a_k=ka_1\ge \sum\limits_{i=1}^ka_i，又因为 \min\limits_{i=1}^ka_i=a_1，所以 ka_1\le \sum\limits_{i=1}^ka_i，所以 ka_1=\sum\limits_{i=1}^ka_i ，所以 \forall i\le k,a_i=k。

定理 5 若 a_n=n+1,\exist i<n,a_i\ge i+1，且 a_{1\sim n} 为好序列，则前缀 a_{1\sim i} 为好序列。

证明：(n+1)a_1\ge \sum\limits_{k=1}^n a_k，则 a_1\ge \sum\limits_{k=1}^n (a_k-a_1)\ge\sum\limits_{k=1}^i (a_k-a_1)，则 a_ia_1\ge (i+1)a_1\ge \sum\limits_{k=1}^i a_k。

分两个情况讨论 a_n=n 和 a_n=n+1，前一种情况是平凡的（因为定理 4），我们只考虑 a_n=n+1，则此时 a 为完美的充要条件为：

但是，我们要求的序列是没有排序的，让我们把每个数都减去 a_1，然后称之为 b。

枚举 a_1，则我们要计数这样的数列 b。

我们设 f_{i,s,k} 为已经确定 i 个元素，当前和为 s，要放置值等于 k 的数的方案数，枚举放了几个 k，f_{i,s,k}=\sum\limits_{j}\frac{f_{i+j,s+jk,k-1}}{j!}，边界为 i=n 时，值为 n! 。

DP 应该是 O(n^3\log n)（\log 是枚举 j 的调和级数），加上枚举 a_i 的复杂度，复杂度为 O(n^4\log n)。

定理 6 a_1<n-2\sqrt n 时，答案为 0。

证明：因为条件至少存在 i(1\le i\le n-a_1) 个数 \ge n+2-i-a_1，若 a_1<n-2\sqrt n，\sum b_i>n+1>a_1，所以无解。

复杂度 O(n^3\sqrt n\log n)，可以通过本题。

#include<cstdio>
#include<cmath>
#include<algorithm>
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull operator ()(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
}mod(2);
int p,n,fac[210],ifac[210];
int pow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=mod(1ll*res*x);
        x=mod(1ll*x*x),y>>=1; 
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&p);
    mod=FastMod(p);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=mod(1ll*fac[i-1]*i);
    ifac[n]=pow(fac[n],p-2);
    for(int i=n;i;i--) ifac[i-1]=mod(1ll*ifac[i]*i);
    int ans=0;
    int lim=2*sqrt(n)+1;
    for(int a1=std::max(1,n-lim);a1<=n;a1++){
        static int f[210][210][210];
        for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) f[i][j][k]=0;
        for(int i=0;i<=n;i++)
            for(int sum=0;sum<=a1;sum++)
                f[i][sum][0]=mod(1ll*fac[n]*ifac[n-i]);
        for(int k=1;k<=n+1-a1;k++){
            for(int i=0;i<n;i++)
                for(int sum=0;sum<=a1;sum++){
                    int &ans=f[i][sum][k];
                    int r=(a1-sum)/k;
                    for(int cnt=std::min(r,n-i);~cnt;--cnt)if(k<=1||i+cnt>=n-a1+2-k){
                        ans=mod(ans+1ll*f[i+cnt][sum+cnt*k][k-1]*ifac[cnt]);
                    }
                }
            for(int sum=0;sum<=a1;sum++) f[n][sum][k]=fac[n];
        }
        ans=mod(ans+f[0][0][n+1-a1]);
    }
    printf("%d\n",ans);
    return 0;
}