题解：P3120 [USACO15FEB] Cow Hopscotch G

· · 题解

题目传送门

分析

首先可以想到最朴素的 DP：f_{i,j} 表示 (i,j) 对答案产生的贡献，则有转移方程：

f_{i,j}=\sum_{k=1}^{i-1}\sum_{l=1}^{j-1}[a_{i,j}\not= a_{k,l}]f_{k,l}

时间复杂度 O(n^4)，需要优化，最首先能想到的显然是二维线段树，但会发现这样空间和时间都会爆掉。

考虑类似 DP 处理的过程，按行来处理，建 k+1 棵线段树，每个节点维护列 [l,r] 中该值的贡献和，第 0 棵节点维护所有值的贡献和，对每行处理时，先统计答案再最后一起修改，这样就保证了线段树里的贡献均不包括当前行的贡献。

但是这样直接建立线段树空间要爆炸，动态开点即可。

普通版本：

#include<bits/stdc++.h>
#define mod 1000000007
#define _ 755
using namespace std;
inline int read(){
    int 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;
}
int n,m,k,a[_][_],now[_];
struct seg{
    int t[_<<2];
    void pushup(int num){t[num]=(t[num<<1]+t[num<<1|1])%mod;}
    void update(int l,int r,int num,int x,int y){
        if(x>r||x<l)return;
        if(x==l&&x==r){t[num]=(t[num]+y)%mod;return;}
        int mid=l+r>>1;
        update(l,mid,num<<1,x,y),update(mid+1,r,num<<1|1,x,y);
        pushup(num);
    }
    int query(int l,int r,int num,int x,int y){
        if(x>r||y<l)return 0;
        if(x<=l&&r<=y)return t[num];
        int mid=l+r>>1;
        return (query(l,mid,num<<1,x,y)+query(mid+1,r,num<<1|1,x,y))%mod;
    }
}t[_*_];
int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();
    t[0].update(1,m,1,1,1),t[a[1][1]].update(1,m,1,1,1);
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            now[j]=(t[0].query(1,m,1,1,j-1)+mod-t[a[i][j]].query(1,m,1,1,j-1))%mod;
        }
        for(int j=1;j<=m;j++){
            t[0].update(1,m,1,j,now[j]);
            t[a[i][j]].update(1,m,1,j,now[j]);
        }
    }
    printf("%d\n",now[m]);
    return 0;
}

动态开点版本：

#include<bits/stdc++.h>
#define mod 1000000007
#define _ 755
using namespace std;
inline int read(){
    int 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;
}
int n,m,k,a[_][_],now[_],rt[_*_];
struct seg{
    int t[_*_<<5],tot,ls[_*_<<5],rs[_*_<<5];
    void pushup(int num){t[num]=(t[ls[num]]+t[rs[num]])%mod;}
    void update(int l,int r,int &num,int x,int y){
        if(!num)num=++tot;
        if(x>r||x<l)return;
        if(x==l&&x==r){t[num]=(t[num]+y)%mod;return;}
        int mid=l+r>>1;
        update(l,mid,ls[num],x,y),update(mid+1,r,rs[num],x,y);
        pushup(num);
    }
    int query(int l,int r,int &num,int x,int y){
        if(!num)num=++tot;
        if(x>r||y<l)return 0;
        if(x<=l&&r<=y)return t[num];
        int mid=l+r>>1;
        return (query(l,mid,ls[num],x,y)+query(mid+1,r,rs[num],x,y))%mod;
    }
}t;
int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();
    t.update(1,m,rt[0],1,1),t.update(1,m,rt[a[1][1]],1,1);
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            now[j]=(t.query(1,m,rt[0],1,j-1)+mod-t.query(1,m,rt[a[i][j]],1,j-1))%mod;
        }
        for(int j=1;j<=m;j++){
            t.update(1,m,rt[0],j,now[j]);
            t.update(1,m,rt[a[i][j]],j,now[j]);
        }
    }
    printf("%d\n",now[m]);
    return 0;
}