Editing 2015 Feb Gold Problem 1 Cow Hopscotch (Gold) (section)

=== C++ ===
<pre>
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
vector<vector<int>> grid;
vector<vector<int>> columns;
vector<BIT*> bits;

class BIT {
    public:
        vector<int> tree;
        vector<int> indices;
        
        BIT(vector<int>& set) {
            indices.resize(set.size() + 2);
            tree.resize(indices.size());
            indices[0] = -1;
            int index = 1;
            for(int out: set) {
                indices[index++] = out;
            }
            indices[indices.size() - 1] = INT_MAX;
        }
        
        void update(int index, int val) {
            int actual = lower_bound(indices.begin(), indices.end(), index) - indices.begin();
            while(actual < indices.size()) {
                tree[actual] += val;
                if(tree[actual] >= MOD) tree[actual] -= MOD;
                actual += actual & -actual;
            }
        }

        int query(int index) {
            int left = 0;
            int right = indices.size() - 1;
            while(left != right) {
                int mid = (left+right+1)/2;
                if(indices[mid] > index) {
                    right = mid-1;
                } else {
                    left = mid;
                }
            }
            int ret = 0;
            while(left > 0) {
                ret += tree[left];
                if(ret >= MOD) ret -= MOD;
                left -= left & -left;
            }
            return ret;
        }
};

void initializeGrid(int r, int c, int colors) {
    grid.resize(r, vector<int>(c));
    columns.resize(colors + 1);

    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> grid[i][j];
        }
    }
}

void processColumns(int r, int c) {
    for(int j = 0; j < c; j++) {
        for(int i = 0; i < r; i++) {
            int color = grid[i][j];
            if(!columns[color].empty() && columns[color].back() == j) continue;
            columns[color].push_back(j);
        }
    }
}

void initializeBits(int colors) {
    bits.resize(colors + 1);
    for(int i = 1; i < bits.size(); i++) {
        if(!columns[i].empty()) {
            bits[i] = new BIT(columns[i]);
        }
    }
}

void processFullBIT(int r, int c, BIT* full) {
    for(int i = 1; i < r - 1; i++) {
        for(int j = c - 2; j > 0; j--) {
            int val = full->query(j - 1) - bits[grid[i][j]]->query(j - 1);
            if(val < 0) val += MOD;
            full->update(j, val);
            bits[grid[i][j]]->update(j, val);
        }
    }
}

int calculateResult(int c, int r, BIT* full) {
    int result = full->query(c - 2) - bits[grid[r - 1][c - 1]]->query(c - 2);
    if(result < 0) result += MOD;
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int r, c, colors;
    cin >> r >> c >> colors;

    initializeGrid(r, c, colors);
    processColumns(r, c);
    initializeBits(colors);

    vector<int> gen(c);
    iota(gen.begin(), gen.end(), 0);
    BIT* full = new BIT(gen);
    full->update(0, 1);
    bits[grid[0][0]]->update(0, 1);

    processFullBIT(r, c, full);

    int result = calculateResult(c, r, full);
    cout << result << '\n';

    return 0;
}

</pre>