给出一个长度为n的序列.求f(0),f(1),f(2),f(3).

其中,f(i)为满足和给出序列的最长公共子序列的长度为i的三元组(x,y,z)的数量.x,y,z为非负整数且不小于m.

链接

题解

2017湘潭邀请赛的题目

设1~m中没有在序列中出现的数字总数为res,序列中互不相同的且不大于m数字个数为tot.根据tot对a进行离散化,超过m的数全部变成0,因为这些数对答案没有影响.预处理出第i个位置后面数字j第一次出现的的位置,以及i前面数字j第一次出现的位置,以及每个数字第一次,最后一次出现的位置.

显然,有f(0)=res^3

对于f(1),有三种情况需要计算:三元组中有一个,两个或三个数在序列中出现过.有一个数出现过的情况的贡献显然为tot*res^2.

对于有两个数在其中出现过的情况,枚举第一个出现的数是什么,将其位置固定在最早出现的地方,然后根据预处理的结果,求出这个位置后面有多少个数没有出现过,记为p.对答案的贡献就是res*p*3.选择最早出现的位置保证了方案的合法性,3倍是因为未出现的数字的位置有三种情况.

剩下是三个数全部出现的情况.枚举中间的数,然后算出在这个数最早出现的位置后面有多少数没有出现,记为p;算出在这个数最后出现的位置前面有多少数没有出现,记为P.对答案的贡献就是p*P.证明较为简单,略过.

f(2)不太好计算,所以先算f(3).因为三个数都出现了,考虑使用记忆化搜索.Dfs(x,p)表示x位置作为三元组的第p位有多少合法方案.每个位置只会被搜到3次,故这部分的时间复杂度为线性的.

最后,f(2)=m*m*m-f(0)-f(1)-f(3).总的时间复杂度为

O(n^{2 })

正解的做法十分简单粗暴.进行相同的预处理后,直接暴力枚举三元组,计算三元组对答案的贡献.时间复杂度为

O(n^{3})

要是我出题,n的范围还能再大一个数量级

别忘了清空数组...

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 210
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,j;
LL res,Ans1,Ans2,Ans3,Ans0,tot,m;
int a[N],b[N],c[N],fr[N],la[N];
int dp[N][N],DP[N][N];
LL g[N][4];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)    c=getchar();
    while (c>=48&&c<=57)  p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Ready(){
    int i=0,j=0;
    for (i=n;i;i--)
        for (j=1;j<=tot;j++)
            dp[i][j]=(a[i+1]==j)?i+1:dp[i][j]=dp[i+1][j];
    for (i=1;i<=n;i++)
        for (j=1;j<=tot;j++)
            DP[i][j]=(a[i-1]==j)?i-1:DP[i][j]=DP[i-1][j];
    for (i=1;i<=n;i++){
        if (!fr[a[i]])  fr[a[i]]=i;
        la[a[i]]=i;
    }
}

inline LL Dfs(int x,int p){
    int i=0;
    LL sum=0;
    if (g[x][p]>=0)  return g[x][p];
    if (p==3)   return g[x][p]=1;
    for (i=1;i<=tot;i++)
        if (dp[x][i])   sum+=Dfs(dp[x][i],p+1);
    return g[x][p]=sum;
}

inline void Work(){
    int i=0,j=0,k=0;
    LL cnt=0,p=0,P=0;
    printf("%lld ",(LL)res*res*res);
    Ans0=(LL)res*res*res;
    // Calulate f(0)

    Ans1=(LL)tot*res*res*3;
    for (i=1;i<=tot;i++){
        k=fr[i];    p=tot;
        for (j=1;j<=tot;j++) p-=(dp[k][j])?1:0;
        Ans1+=res*p*3;
    }
    // 0 1 x *3
    for (i=1;i<=tot;i++){
        k=fr[i];    p=tot;
        for (j=1;j<=tot;j++) p-=(dp[k][j])?1:0;
        k=la[i];    P=tot;
        for (j=1;j<=tot;j++) P-=(DP[k][j])?1:0;
        Ans1+=p*P;
    }
    // 0 1 0
    printf("%lld ",Ans1);
    // Calulate f(1)

    memset(g,-1,sizeof(g)); Ans3=0;
    for (i=1;i<=tot;i++) Ans3+=Dfs(fr[i],1);
    Ans2=(LL)m*m*m-Ans0-Ans1-Ans3;
    printf("%lld %lld\n",Ans2,Ans3);
}

int main(){
    while (~scanf("%d%lld",&n,&m)){
        memset(c,0,sizeof(c));  res=m;  tot=0;
        memset(dp,0,sizeof(dp));    memset(DP,0,sizeof(DP));
        memset(fr,0,sizeof(fr));    memset(la,0,sizeof(la));
                memset(a,0,sizeof(a));  memset(b,0,sizeof(b));
        for (i=1;i<=n;i++)   b[i]=a[i]=read();
        sort(b+1,b+1+n);
        for (i=1;i<=n;i++){
            if (b[i]!=b[i-1]&&b[i]<=m)   res--;
            if (b[i]!=b[i-1]&&b[i]<=m)   c[++tot]=b[i];
        }
        if (n==1)   {
            cout<<res<<" 1 0 0"<<endl;
            continue;
        }   else if (n==2) {
            cout<<res*res<<" "<<m*m-1-res*res<<" 1 0\n";
            continue;
        }
        for (i=1;i<=n;i++){
            for (j=1;j<=tot;j++)
                if (a[i]==c[j]) {a[i]=j;    break;}
            if (a[i]>m)  a[i]=0;
        }
        Ready();    Work();
    }
    return 0;
}