[USACO 2015 Gold] Cow Hopscotch

作法：

記 dp[ i ][ j ] 代表從左上角開始，有多少種方法可以跳到 [ i ][ j ] 這格。假設現在要算第 i 排的所有位置的答案，那麼我們可以先預處理出 sum 陣列，其中 sum[ j ] = dp 表格中 ( 1 , 1 ) 和 ( i-1 , j ) 形成的矩形內的所有數的總和，那麼 dp[ i ][ j ] 的算法就是用 sum[ j-1 ] ，扣掉「( 1 , 1 ) 和 ( i-1 , j ) 形成的矩形內，和顏色和 [ i ][ j ] 相同的格子的數的總和」。因此一個作法就是直接對每個顏色都維護一個和 sum 一樣的前綴和陣列，大小和原圖的寬度一樣。但這樣顯然記憶體會不夠。事實上只要注意到，其實有很多直行根本就沒有某個顏色，那麼這一直行對這個顏色的總和值貢獻永遠是 0 ，因此對於每個顏色，我們的陣列的大小只需要開「有幾個直行有這個顏色」就夠了，並且把所有的直行位置都記錄起來，才能知道當前這個直行會對應到現在這個顏色屬於的前綴和陣列中的哪個位子。但每次做完一整排的答案之後還必須對所有的顏色重算一次前綴和，這樣太慢了，如果改成 BIT 就可以在每次 log n 的時間內修改，並且所有顏色的格子數總和為 n*m ，這樣複雜度就可以降到 O( n*m*logn ) 了。

code :

#include<bits/stdc++.h>
#define MOD 1000000007
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=750+10 ;
 
vector<int> bit[maxn*maxn] ;
void add(int id,int x,int val)
{
    while(x<bit[id].size())
        bit[id][x]=(bit[id][x]+val)%MOD ,
        x+=lowbit(x) ;
}
int query(int id,int x)
{
    int ret=0 ;
    while(x) ret=(ret+bit[id][x])%MOD , x-=lowbit(x) ;
    return ret ;
}
 
vector<int> col[maxn*maxn] ;
int G[maxn][maxn],dp[maxn][maxn] ;
int sum[maxn] ;
 
main()
{
    if(fopen("hopscotch.in","r"))
    {
        freopen("hopscotch.in","r",stdin) ;
        freopen("hopscotch.out","w",stdout) ;
    }
 
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        scanf("%d",&G[i][j]) ;
        col[G[i][j]].push_back(j) ;
    }
    for(int i=1;i<=k;i++)
    {
        sort(col[i].begin(),col[i].end()) ;
        col[i].resize(unique(col[i].begin(),col[i].end())-col[i].begin()) ;
        bit[i].resize(col[i].size()+1) ;
    }
 
    dp[1][1]=1 ;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1 || j==1) continue ;
            int c=G[i][j] ;
            int id=lower_bound(col[c].begin(),
                    col[c].end(),j) - col[c].begin() + 1 ;
            dp[i][j]=(sum[j-1]-query(c,id-1))%MOD ;
            if(dp[i][j]<0) dp[i][j]+=MOD ;
        }
        for(int j=1,s=0;j<=m;j++)
        {
            s=(s+dp[i][j])%MOD ;
            sum[j]=(sum[j]+s)%MOD ;
            int c=G[i][j] ;
            int id=lower_bound(col[c].begin(),
                    col[c].end(),j) - col[c].begin() + 1 ;
            add(c,id,dp[i][j]) ;
        }
    }
    printf("%d\n",dp[n][m]) ;
}