题目概述

AtCoder Regular Contest 104E

解题报告

这题还是挺可做的。我们发现 $n$ 小的一批，因此考虑离散。我们没必要对于每个 $i$ 都枚举 $1\to A_i$ ，对于每一个 $[A_{i-1}+1,A_{i}-1]$ ，我们只需要知道这之间有多少个不同的数和他们之间的大小关系就可以求出方案数。

我们对于 $[A_{i-1}+1,A_i-1]$ ，只保留最多 $n$ 个数，用来确定个数和大小关系。然后直接爆搜，求LIS和方案数。

统计的时候要注意去重，比如 $[1,5]$ 中，选了 $1,3,4$ 和选了 $1,2,3$ 是等价的，需要去重。

复杂度 $O(\prod_{i=1}^{n}i(n+1))$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=6,maxm=42,MOD=1e9+7;

int n,a[maxn+5],ID[maxn+5],c[maxn+5];
int N,m,pos[maxm+5],sum[maxn+5],INV[maxn+5];bool ex[maxm+5];
int ans,x[maxn+5],cnt[maxn+5],f[maxn+5];bool vis[maxm+5];

inline bool cmp(const int &i,const int &j) {return a[i]<a[j];}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;}
int C(int x,int y) {int c=1;for (int i=1;i<=y;i++) c=MUL(c,MUL(x-i+1,INV[i]));return c;}
void Count(){
    for (int i=1;i<=m;i++) if (!ex[i] && !ex[i-1] && !vis[i-1] && vis[i]) return;
    int tot=1,LIS=0;for (int i=1;i<=N;i++) tot=MUL(tot,C(sum[i],cnt[i]));
    for (int i=1;i<=n;i++){
        f[i]=1;for (int j=1;j<i;j++) if (x[j]<x[i] && f[j]+1>f[i]) f[i]=f[j]+1;
        if (f[i]>LIS) LIS=f[i];
    }
    ans=ADD(ans,MUL(LIS,tot));
}
void DFS(int st){
    if (st>n) return Count();
    for (int i=1;i<=c[st];i++){
        bool fl=vis[i];x[st]=i;if (!fl) vis[i]=true,cnt[pos[i]]++;
        DFS(st+1);if (!fl) vis[i]=false,cnt[pos[i]]--;
    }
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),ID[i]=i;
    sort(ID+1,ID+n+1,cmp);ex[0]=true;
    for (int i=1,j;i<=n;i=j){
        for (j=i+1;j<=n && a[ID[i]]==a[ID[j]];j++); N++;
        for (int k=a[ID[i-1]]+1,cnt=0;k<a[ID[i]] && cnt<n;k++) pos[++m]=N,cnt++;
        m++;ex[m]=true;sum[N]=a[ID[i]]-a[ID[i-1]]-1;
        for (int k=i;k<j;k++) c[ID[k]]=m;
    }
    for (int i=1;i<=n;i++) INV[i]=Pow(i,MOD-2);DFS(1);
    int D=1;for (int i=1;i<=n;i++) D=MUL(D,a[i]);ans=MUL(ans,Pow(D,MOD-2));
    printf("%d\n",ans);return 0;
}