「PMOI-3」期望乘积题解

ducati · 2021-03-28 19:45:15 · 题解

Description

ducati 热爱定义一些奇奇妙妙的东西。

定义两个序列不同，当且仅当它们的长度不同，或者它们长度相同但存在至少一组对应位上的值不同。
定义序列 A 的权值为 A 中所有数的乘积。
定义序列间的可达如下：
- 做恰好 t 次操作，每次操作选择 A 的一个子区间（注意，选定的子区间可以为空）并将子区间中的数加 1 ；若存在一种操作方案，使得操作结束后 A 与 B 完全相同，则称 A 可达 B。
定义序列 A 的优美值为所有 A 可达的不同序列的权值和。

现在，ducati 拥有了一个长度为 n 的序列 a。他会多次查询一段区间的优美值。

你能帮帮好奇的他吗？你只需要输出每个答案对 10007 取模的值就行啦。

1 \le n,q \le 10^5

Solution

Subtask 1

爆搜即可。

期望得分 10 分。

Subtask 2

不难发现，我们实际上就是要求出，所有满足对 a[l \sim r] 进行不超过 t 次操作可以达到的 b 的权值和。注意，确定下了 b 之后，从 a 变为 b 的最少操作次数就是 P1969。

考虑 dp 。

令 f_{i,j,k} 表示，目前考虑到第 i 个数，a_i 被加了 j 次 1 ，且要想达到当前的 b 至少需要操作 k 次。

根据 P1969 的套路，不难得到状态转移式：

f_{i,j,k}=\sum_{p=0}^j f_{i-1,p,k-(j-p)}(a_i+j) + \sum_{p=j+1}^k f_{i-1,p,k} (a_i+j)

第一个 \sum 表示 j \ge p 的情况，此时总操作次数要添加 j-p 次；第二个 \sum 表示 j<p 的情况，总操作次数不需增加。

边界: f_{l-1,0,0}=1

答案：\sum_{x=0}^t \sum_{y=0}^t dp_{r,x,y}

时间复杂度 O(nt^3)，期望得分 30 分。

Subtask 3

为了方便叙述，我们将这个三维 dp 通过映射变为一个等价的二维 dp 。具体地说，f_{i,j,k} 被映射到了 g_{i,(j-1)t+k}。

考虑使用矩阵乘法来完成这个转移。

我们先处理出序列中每个位置的转移矩阵并建立出一棵线段树，维护区间内的矩阵乘积。

每次询问的时候，我们在线段树上找到那 \log n 个被划分出来的区间，并将这些矩阵给乘起来即可。

时间复杂度 O(nt^6+q \log n \ t^6) 。

期望得分 60 分。

Subtask 4

考虑优化。

在每次询问的时候，我们先定义一个向量，其 1 至 t 位均为 0，且第 0 位为 1 。我们在线段树上找到那 \log n 个被划分出来的区间，然后直接向量乘矩阵即可。

考虑到当 t=3 时每个矩阵的边长都是 10 ，于是总时间复杂度为

O(10^3 n+10^2 \ q \log n)

期望得分 100 分。

Summary

本题主要考察了选手的 dp 设计能力与优化能力，同时也考察了小数据结构与一些经典的优化套路(如向量乘矩阵，单次矩阵乘法对取模次数的优化)。

值得一提的是，本题似乎还可以通过矩阵前缀和以及矩阵求逆来解出。它虽然时间复杂度更为优秀（少一个 \log n），但是它常数较大，有可能会被卡掉。

Code

#include <bits/stdc++.h>
#define PA pair<int,int>
#define fi first
#define se second
#define MP make_pair
using namespace std;
const int maxl=100005,mod=10007;

int read(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
    while (ch>='0'&&ch<='9'){s=s*10+(ch^'0');ch=getchar();}
    return s*w;
}
int n,q,t,blo,now,ans,le,ri,tot;
int a[maxl],pos[11][11],lis[11];

struct Matrix{int a[11][11];}tmp[maxl];

struct Segment_tree{
    int lson,rson,prod;
    Matrix p;
}tree[maxl<<1];

Matrix operator * (const Matrix &x,const Matrix &y){
    Matrix z;
    for (int i=0;i<=blo;i++){
        for (int j=0;j<=blo;j++){
            z.a[i][j]=0;
            for (int k=0;k<=blo;k++)  z.a[i][j]+=x.a[i][k]*y.a[k][j];
            z.a[i][j]%=mod;
        }
    }
    return z;
}

void pushup(int rt){
    int l=tree[rt].lson,r=tree[rt].rson;
    tree[rt].p = tree[l].p * tree[r].p;
    tree[rt].prod = (tree[l].prod * tree[r].prod) % mod;
}

int build_tree(int l,int r,int rt){
    rt=++tot;
    if (l==r){
        tree[rt].prod=a[l];
        tree[rt].p=tmp[l];
        return rt;
    }
    int mid=(l+r)>>1;
    tree[rt].lson=build_tree(l,mid,0);
    tree[rt].rson=build_tree(mid+1,r,0);

    pushup(rt);

    return rt;
}

int query_prod(int nl,int nr,int l,int r,int rt){
    if (nl<=l&&r<=nr){
        return tree[rt].prod;
    }
    int mid=(l+r)>>1,res=1;
    if (nl<=mid)  res = query_prod(nl,nr,l,mid,tree[rt].lson);
    if (nr>mid)  res *= query_prod(nl,nr,mid+1,r,tree[rt].rson);

    return res%mod;
}

void query_seg(int nl,int nr,int l,int r,int rt){
    if (nl<=l && r<=nr){
        int tmp[10];
        for (int i=0;i<=blo;i++)  tmp[i]=0;
        for (int i=0;i<=blo;i++){
            for (int j=0;j<=blo;j++){
                tmp[j] += lis[i] * tree[rt].p.a[i][j];
            }
        }
        for (int i=0;i<=blo;i++)  lis[i] = tmp[i]%mod;
        return;
    }
    int mid=(l+r)>>1;
    if (nl<=mid)  query_seg(nl,nr,l,mid,tree[rt].lson);
    if (nr>mid)  query_seg(nl,nr,mid+1,r,tree[rt].rson);
}

signed main(){
    n=read(),q=read(),t=read();
    for (int i=1;i<=n;i++)  a[i]=read();

    if (t){
        blo=((t+1)*(t+2))/2;
        for (int i=0;i<=t;i++){
            for (int j=i;j<=t;j++){
                pos[i][j]=now;
                now++;
            }
        }
        for (int i=1;i<=n;i++){
            for (int j=0;j<=t;j++){
                int val=a[i]+j;
                for (int k=j;k<=t;k++){
                    for (int p=0;p<=k;p++){
                        if (p<j){
                            if (k-j+p>=0)  tmp[i].a[pos[p][k-j+p]][pos[j][k]]=val;
                        }
                        else tmp[i].a[pos[p][k]][pos[j][k]]=val;
                    }
                }
            }
        }
    }
    build_tree(1,n,1);
    while (q--){
        le=read(),ri=read();
        if (t==0){
            ans = query_prod(le,ri,1,n,1);
        } 
        else{
            memset(lis,0,sizeof(lis));
            lis[0]=1,ans=0;

            query_seg(le,ri,1,n,1);
            for (int i=0;i<=t;i++)  ans=(ans+lis[pos[i][t]])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

「PMOI-3」期望乘积 题解