include

include

include

using namespace std;

const int md = 1000000007;

// Function to add two vectors element-wise vector add(vector a, vector b) { int n = a.size(); int m = b.size(); int k = (n > m ? n : m); vector c(k); for (int i = 0; i < k; i++) { if (i >= n) c[i] = b[i]; else if (i >= m) c[i] = a[i]; else c[i] = (a[i] + b[i]) % md; } return c; }

// Function to multiply a vector by a constant vector mul(vector a, int b) { int n = a.size(); for (int i = 0; i < n; i++) { a[i] = ((long long)a[i] * b) % md; if (a[i] < 0) a[i] += md; } return a; }

// Function to multiply a vector by (x - bb) vector mul_x(vector a, int bb) { vector b(1, 0); b.insert(b.end(), a.begin(), a.end()); vector c = mul(a, -bb); return add(b, c); }

// Evaluate a polynomial represented by a vector for a given x int eval(vector a, int x) { int ans = 0, y = 1; for (int i = 0; i < (int)a.size(); i++) { ans = (ans + (long long)y * a[i]) % md; y = (long long)y * x % md; } return ans; }

// Normalize the vector by assigning consecutive numbers to non-zero elements void normalize(vector &a) { int n = a.size(); vector color(n + 3, 0); int last = 0; for (int i = 0; i < n; i++) { if (a[i] == 0) { continue; } if (color[a[i]] == 0) { color[a[i]] = ++last; } a[i] = color[a[i]]; } }

map, vector> f[10][10]; // Map to store intermediate results map, vector>::iterator it; vector result[10][10]; // Stores final results

int main() { // Pre-computation for (int rows = 1; rows <= 8; rows++) { for (int i = 0; i < rows; i++) for (int j = 0; j <= 8; j++) f[i][j].clear();

    vector<int> temp(rows, 0);
    f[0][0][temp] = vector<int>(1, 1);

    for (int col = 0; col < 8; col++) {
        for (int row = 0; row < rows; row++) {
            int n_col = col;
            int n_row = row;
            if (n_row + 1 < rows) {
                n_row++;
            } else {
                n_row = 0;
                n_col++;
            }

            it = f[row][col].begin();
            while (it != f[row][col].end()) {
                vector<int> state = (*it).first;
                vector<int> poly = (*it).second;
                int maxc = 0;
                for (int i = 0; i < rows; i++)
                    if (state[i] > maxc)
                        maxc = state[i];

                for (int c = 1; c <= maxc; c++) {
                    if (c == state[row]) {
                        continue;
                    }
                    if (row > 0 && c == state[row - 1]) {
                        continue;
                    }
                    vector<int> new_state = state;
                    new_state[row] = c;
                    normalize(new_state);
                    f[n_row][n_col][new_state] = add(f[n_row][n_col][new_state], poly);
                }

                vector<int> new_state = state;
                new_state[row] = maxc + 1;
                normalize(new_state);
                vector<int> new_poly = mul_x(poly, maxc);
                f[n_row][n_col][new_state] = add(f[n_row][n_col][new_state], new_poly);

                it++;
            }
        }
    }

    for (int cols = 1; cols <= 8; cols++) {
        result[rows][cols] = vector<int>();
        it = f[0][cols].begin();
        while (it != f[0][cols].end()) {
            vector<int> poly = (*it).second;
            result[rows][cols] = add(result[rows][cols], poly);
            it++;
        }
    }
}

int tt;
scanf("%d", &tt);
while (tt--) {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", eval(result[n][m], k));
}

return 0;

}

Need more insight on the Grid coloring condition. The number of distinct colors on the right should be equal to the number of distinct colors on the left.

I'm not sure if anyone is interested, but here are some thoughts about this problem that might be useful to someone.

First, it is important to know that for any graph G there is a polynomial P_G(k) which gives the number of ways the graph can be colored with (up to) k colors. This polynomial P_G(k) is called the chromatic polynomial of G, and many of its properties are well-known to mathematicians.

One property of the chromatic polynomial that is relevant in this problem is the fact that its degree is equal to the number of nodes in the graph. For the grid graphs in this problem, this degree will not exceed sixty-four; but we may be asked about a particular grid graph a large number of times. Because a degree MxN polynomial is completely determined by its values for MxN different inputs, we can see that essentially we are being asked to compute the chromatic polynomials for the grid graphs in question.

The second important thing to know is that, as of this writing, there is no known simple, closed-form formula for the chromatic polynomial of an arbitrary grid graph. (If you discover one, you should publish it.) There are well-known algorithms for computing chromatic polynomials of arbitrary graphs, but they are terribly inefficient. So we don't have many options available to us:

• We can use a symbolic math package like Mathematica or Maple to find out the chromatic polynomials for all of the graphs we need. This works, but arguably it wastes an opportunity to learn something interesting.
• We can write our own program to compute the chromatic polynomial of an arbitrary graph, using the well-known contraction-deletion algorithm. Making this run in a reasonable amount of time is not easy: a naive implementation will end up either contracting or deleting up to 49 edges. A simple recursion through a tree with 2^49 leaf nodes is going to take a while.
• We can write our own program to compute the chromatic polynomial of a grid graph, specifically. This is doable, but takes a little bit of thinking. The basic observation is that the number of ways to extend a grid graph by adding one more row depends only on the pattern of colors in the previous row; so there is the possibility here of calculating how many ways the graph can be colored row by row.

A final thought is that, even with a decent idea and a decent implementation, it is very difficult to get an algorithm that will compute the chromatic polynomial of a grid graph without exceeding the time limits for the test cases. So a different approach is to write something that can run in a few minutes, and then hard-code the results into the program that actually passes the test cases.

OK, I'll stop with that. Hopefully these thoughts might be enough to encourage someone to make some progress on this challenge. Good luck.

include

include

include

include

include

include

using namespace std;

const int md = 1000000007;

vector add(vector a, vector b) { int n = a.size(); int m = b.size(); int k = (n > m ? n : m); vector c(k); for (int i = 0; i < k; i++) if (i >= n) c[i] = b[i]; else if (i >= m) c[i] = a[i]; else c[i] = (a[i] + b[i]) % md; return c; }

vector mul(vector a, int b) { int n = a.size(); for (int i = 0; i < n; i++) { a[i] = ((long long)a[i] * b) % md; if (a[i] < 0) a[i] += md; } return a; }

vector mul_x(vector a, int bb) { vector b(1, 0); b.insert(b.end(), a.begin(), a.end()); vector c = mul(a, -bb); return add(b, c); }

int eval(vector a, int x) { int ans = 0, y = 1; for (int i = 0; i < (int)a.size(); i++) { ans = (ans + (long long)y * a[i]) % md; y = (long long)y * x % md; } return ans; }

void normalize(vector &a) { int n = a.size(); vector color(n + 3, 0); int last = 0; for (int i = 0; i < n; i++) { if (a[i] == 0) { continue; } if (color[a[i]] == 0) { color[a[i]] = ++last; } a[i] = color[a[i]]; } }

map < vector , vector > f[10][10]; map < vector , vector >::iterator it; vector result[10][10];

int main() { for (int rows = 1; rows <= 8; rows++) { for (int i = 0; i < rows; i++) for (int j = 0; j <= 8; j++) f[i][j].clear(); vector temp(rows, 0); f[0][0][temp] = vector (1, 1); for (int col = 0; col < 8; col++) { for (int row = 0; row < rows; row++) { int n_col = col; int n_row = row; if (n_row + 1 < rows) { n_row++; } else { n_row = 0; n_col++; } it = f[row][col].begin(); while (it != f[row][col].end()) { vector state = (*it).first; vector poly = (*it).second; int maxc = 0; for (int i = 0; i < rows; i++) if (state[i] > maxc) maxc = state[i]; for (int c = 1; c <= maxc; c++) { if (c == state[row]) { continue; } if (row > 0 && c == state[row - 1]) { continue; } vector new_state = state; new_state[row] = c; normalize(new_state); f[n_row][n_col][new_state] = add(f[n_row][n_col][new_state], poly); } vector new_state = state; new_state[row] = maxc + 1; normalize(new_state); vector new_poly = mul_x(poly, maxc); f[n_row][n_col][new_state] = add(f[n_row][n_col][new_state], new_poly); it++; } } } for (int cols = 1; cols <= 8; cols++) { result[rows][cols] = vector (); it = f[0][cols].begin(); while (it != f[0][cols].end()) { vector poly = (*it).second; result[rows][cols] = add(result[rows][cols], poly); it++; } } } int tt; scanf("%d", &tt); while (tt--) { int n, m, k; scanf("%d %d %d", &n, &m, &k); printf("%d\n", eval(result[n][m], k)); } return 0; }

Any hope to get an editorial here? Was able to calculate it for 2-x and 3-x graphs, but nothing more.