P6009

cwfxlh · 2023-07-14 20:25:55 · 题解

P6009

模拟赛考了这道题，但不知道为什么没做出来。

DP 式子的转移是很好列的，令 dp_{i} 表示当前以值为 i 的元素结尾的不降子序列个数，特别的，令 dp_0 表示空序列个数，则令当前枚举到了第 j 个元素，转移为 dp_{A_j}+=\sum_{u=0}^{A_j}dp_u。很容易发现这个东西可以写成矩阵的形式，于是问题就变成了一个区间矩阵乘积的问题。我们不妨用前缀积与逆前缀积来维护。但是我们发现，转移写成的矩阵逆是很好求的，不需要高消求逆（数学计算推一下即可，形式与原矩阵相似），于是直接暴力乘出一个前缀积和逆前缀积，询问的时候相乘即可。复杂度 O((n+q)k^3)。

但是这个复杂度是过不去的，我们发现，转移写出来的矩阵只有 O(k) 个元素有值，于是预处理的矩乘就可以加速到 O(nk^2)。询问的时候，答案矩阵可以由 base\times InvPre(L-1)\times Pre(R) 得到，其中 base 是一个仅有一个元素为 1 的 1\times (k+1) 的矩阵，于是乘上 base 后，矩阵大小只有 k+1，暴力矩阵乘的复杂度会变为 O(qk^2)，可以通过此题。当然利用前缀和可以优化到 O(qk)。总复杂度 O((n+q)k^2)。

代码：

#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
using namespace std;
struct Matrix{
    int h;
    int w;
    int v[23][23];
}InvPre[50003],Pre[50003],res,ans;
Matrix operator*(Matrix A,Matrix B){
    res.h=A.h;
    res.w=B.w;
    for(int i=1;i<=res.h;i++){
        for(int j=1;j<=res.w;j++){
            res.v[i][j]=0;
            for(int u=1;u<=A.w;u++)res.v[i][j]=(res.v[i][j]+((ll)(A.v[i][u])*(ll)(B.v[u][j])%MOD))%MOD;
        }
    }
    return res;
}
void print(Matrix A){
    for(int i=1;i<=A.h;i++){
        for(int j=1;j<=A.w;j++)printf("%d ",(A.v[i][j]+MOD)%MOD);
        printf("\n");
    }
    return;
}
int n,k,q,w[50003],op1,op2,sum;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    scanf("%d",&q);
    Pre[0].h=Pre[0].w=InvPre[0].h=InvPre[0].w=k+1;
    for(int i=1;i<=k+1;i++)Pre[0].v[i][i]=InvPre[0].v[i][i]=1;
    for(int i=1;i<=n;i++){
        Pre[i].h=Pre[i].w=InvPre[i].h=InvPre[i].w=k+1;
        Pre[i]=Pre[i-1];
        for(int u=1;u<=k+1;u++){
            for(int p=1;p<=w[i]+1;p++)Pre[i].v[u][w[i]+1]=(Pre[i].v[u][w[i]+1]+Pre[i-1].v[u][p])%MOD;
        }
        for(int j=1;j<=k+1;j++){
            for(int u=1;u<=k+1;u++){
                InvPre[i].v[j][u]=(InvPre[i-1].v[j][u]-(500000004ll*(ll)(InvPre[i-1].v[w[i]+1][u])*(ll)(j<=w[i]+1))%MOD)%MOD;
            }
        }
    }
    while(q--){
        scanf("%d%d",&op1,&op2);
        ans.h=1;
        ans.w=k+1;
        for(int i=1;i<=k+1;i++)ans.v[1][i]=(int)(i==1);
        ans=(ans*InvPre[op1-1]);
        ans=(ans*Pre[op2]);
        sum=0;
        for(int i=1;i<=k+1;i++)sum=(sum+ans.v[1][i])%MOD;
        sum+=MOD;
        sum%=MOD;
        printf("%d\n",sum);
    }
    return 0;
}