P10138 [USACO24JAN] Cowmpetency G

· · 题解

思路：

感觉不错，中等蓝吧……

考虑对第 i 个数有三种可能的状态 -1/1/0 分别表示：不可能是严格前缀最大值；一定是严格前缀最大值；可能是前缀最大值。

那么我们需要对于一个限制 (x,y)，确定一些位置的状态。

因为该限制需要满足：

\max\limits_{i=x+1}^y a_i \le \max\limits_{i=1}^x a_i < a_y

则区间 [x+1,y-1] 不可能是严格前缀最大值，状态为 -1；且单点 y 一定是严格前缀最大值。

经过这样的判断，如果一个点既一定又不可能，那么就无解。

然后考虑动态规划算法，定义 dp_{i,j} 表示考虑序列 a 中前 i 项，其前缀最大值为 j 时的可能方案，则状态转移方程为：

dp_{i,j}=\begin{cases} dp_{i-1,j} \times j & op_i=-1\\ \sum\limits_{k=1}^{j-1} dp_{i-1,k} + dp_{i-1,j} \times j& op_i = 0 \\ \sum\limits_{k=1}^{j-1} dp_{i-1,k}& op_i = 1\end{cases}

很容易想到用前缀和优化，定义：

s_{i,j}=\sum_{k=1}^j dp_{i,k}

状态转移方程优化为：

dp_{i,j}=\begin{cases} dp_{i-1,j} \times j & op_i=-1\\ s_{i-1,j-1} + dp_{i-1,j} \times j& op_i = 0 \\ s_{i-1,j-1} & op_i = 1\end{cases}

时间复杂度为 O(NC)，至此，我们已经获得了 75pts 的好成绩。

但是因为 N 实在是太大了，重复的状态段特别多，考虑缩段，将连续的一段 0 和 -1 缩为一个点，因为状态为 1 的个数是 O(q) 级别的，可以不用缩点，而且缩点之后的状态转移不好计算。

定义第 i 段的长度为 A_i，状态为 OP_i，即若 OP_i=1，则 A_i=1；然后定义 dp_{i,j} 表示前 i 段的前缀最大值为 j 的方案数，则状态转移方程为：

dp_{i,j}=\begin{cases} dp_{i-1,j} \times j^{A_i} & OP_i = -1 \\ f(A_i,j) \sum\limits_{k=1}^{j-1} dp_{i-1,k} + dp_{i-1,j} \times j^{A_i}& OP_i = 0 \\ \sum\limits_{k=1}^{j-1} dp_{i-1,k} & OP_i = 1\end{cases}

其中 f(x,y) 表示 x 个在 [1,y] 范围内的数，出现至少一个 y 的方案数，则相当于任意取的方案数减去不出现 y 的方案数：

f(x,y)=y^x-(y-1)^x

这个也可以进行前缀和优化：

dp_{i,j}=\begin{cases} dp_{i-1,j} \times j^{A_i} & OP_i = -1 \\ f(A_i,j) \times s_{i-1,j-1} + dp_{i-1,j} \times j^{A_i}& OP_i = 0 \\ s_{i-1,j-1} & OP_i = 1\end{cases}

这样加上快速幂的计算，时间复杂度为 O(QC \log n)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll Q=505,N=10100,mod=1e9+7; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct St{
    ll l,r;
    bool operator<(const St&rhs)const{
        if(r==rhs.r)
          return l<rhs.l;
        return r<rhs.r;
    }
}h[N];
ll n,q,c,cnt=0,l=1;
ll A[Q],op[Q];
ll dp[Q][N],s[Q][N];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1ll)
          ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1ll;
    }
    return ans;
}
int main(){
//  freopen("A.in","r",stdin);
//  freopen("A.out","w",stdout);
    n=read(),q=read(),c=read();
    for(int x,y,i=1;i<=q;i++){
        x=read(),y=read();
        h[i]={x+1,y};
    }
    sort(h+1,h+q+1);
    for (int i=1;i<=q;i++){
        if(h[i].r==h[i-1].r)
          continue;
        if(l>h[i].l){
            puts("0");
            exit(0);
        }
        if(l<h[i].l){
            cnt++;
            A[cnt]=h[i].l-l;
            op[cnt]=0;
        }
        if(h[i].l<h[i].r){
            cnt++;
            A[cnt]=h[i].r-h[i].l;
            op[cnt]=-1;
        }
        cnt++;
        A[cnt]=1;
        op[cnt]=1;
        l=h[i].r+1;
    }
    if(h[q].r<n){
        cnt++;
        A[cnt]=n-h[q].r;
        op[cnt]=0;
    }
//  for(int i=1;i<=cnt;i++){
//      write(op[i]);
//      putchar(' ');
//  }
//  putchar('\n');
    dp[0][0]=1;
    for(int i=0;i<=c;i++)
      s[0][i]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=c;j++){
            ll x=qpow(j,A[i]),y=qpow(j-1,A[i]);
            if(op[i]==-1)
              dp[i][j]=(dp[i-1][j]*x)%mod;
            else if(!op[i])
              dp[i][j]=(((x-y+mod)%mod*s[i-1][j-1])%mod+(dp[i-1][j]*x)%mod)%mod;
            else
              dp[i][j]=s[i-1][j-1];
            s[i][j]=(s[i][j-1]+dp[i][j])%mod;
        }
    }
//  for(int i=1;i<=cnt;i++){
//      for(int j=1;j<=c;j++){
//          write(s[i][j]);
//          putchar(' ');
//      }
//      putchar('\n');
//  }
    write(s[cnt][c]);
    return 0;
}