Challenge: Coloring Grid
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 80.0 / 80
Submission status: Accepted
Submission score: 1.0
Submission ID: 464791811
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/coloring-grid/problem
Cerinta
Calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge.
**Input Format**
The first line contains an integer T denoting the number of test-cases.
The next T lines contains integers N, M and K separated by a single space.
**Output Format**
Output T lines, one for each test case containing the number of ways modulo 10<sup>9</sup>+7.
**Constraints**
1 <= T <= 10<sup>5</sup>
1 <= N,M <= 8
1 <= K <= 10<sup>9</sup>
**Sample Input**
3
3 3 2
3 4 3
1 1 1
**Sample Output**
2
1122
1
**Explanation**
For the first case, there are two ways to color the grid. The colorings are in a chessboard pattern with either color at the top right square.
**Timelimits**
Timelimits for this challenge can be seen [here](https://www.hackerrank.com/environment)Cod sursa
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
const long long MOD = 1000000007;
// W[N][M][C] represents the number of valid colorings of an N x M grid exactly using C unlabelled colors.
long long W[9][9][65];
map<vector<int>, int> prof_to_id;
vector<vector<int>> id_to_prof;
// Normalizes a coloring sequence to abstract its equivalence relation.
int get_id(const vector<int>& p) {
vector<int> norm(p.size());
int m[20];
for (int i = 0; i < 20; ++i) m[i] = -1;
int nxt = 0;
for (int i = 0; i < (int)p.size(); ++i) {
if (m[p[i]] == -1) m[p[i]] = nxt++;
norm[i] = m[p[i]];
}
auto it = prof_to_id.find(norm);
if (it != prof_to_id.end()) return it->second;
int id = (int)prof_to_id.size();
prof_to_id[norm] = id;
id_to_prof.push_back(norm);
return id;
}
// Caches to avoid redundant expensive normalizations
int trans_in[5005][10][2];
int trans_out[5005][2];
// Precomputes values iteratively using dynamic programming
void precompute() {
for (int M = 1; M <= 8; ++M) {
prof_to_id.clear();
id_to_prof.clear();
memset(trans_in, -1, sizeof(trans_in));
memset(trans_out, -1, sizeof(trans_out));
vector<vector<long long>> dp;
int dummy_id = get_id({});
(void)dummy_id;
dp.resize(1);
dp[0].resize(65, 0);
dp[0][0] = 1;
// Given N <= M symmetry, we can just process cells up to M * M.
for (int i = 0; i < M * M; ++i) {
int r = i / M;
int c = i % M;
int r_gt_0 = (r > 0 ? 1 : 0);
vector<vector<long long>> next_dp(id_to_prof.size(), vector<long long>(65, 0));
for (int id = 0; id < (int)dp.size(); ++id) {
// Pruning empty tracks
bool has_any = false;
for (int C = 0; C <= i; ++C) {
if (dp[id][C]) { has_any = true; break; }
}
if (!has_any) continue;
vector<int> prof = id_to_prof[id];
int c_prof = 0;
for (int x : prof) c_prof = max(c_prof, x);
if (!prof.empty()) c_prof += 1;
int forbidden_above = (r > 0) ? prof[0] : -1;
int forbidden_left = (c > 0) ? prof.back() : -1;
// Option 1: Pick a valid matching color from current profile window
for (int x = 0; x < c_prof; ++x) {
if (x != forbidden_above && x != forbidden_left) {
int nid = trans_in[id][x][r_gt_0];
if (nid == -1) {
vector<int> nprof = prof;
if (r > 0) nprof.erase(nprof.begin());
nprof.push_back(x);
nid = get_id(nprof);
trans_in[id][x][r_gt_0] = nid;
}
if (nid >= (int)next_dp.size()) next_dp.resize(nid + 1, vector<long long>(65, 0));
for (int C = 0; C <= i; ++C) {
if (long long val = dp[id][C]) {
next_dp[nid][C] = (next_dp[nid][C] + val) % MOD;
}
}
}
}
// Cache ID generation for "off-profile" colors
int nid = trans_out[id][r_gt_0];
if (nid == -1) {
vector<int> nprof = prof;
if (r > 0) nprof.erase(nprof.begin());
nprof.push_back(c_prof);
nid = get_id(nprof);
trans_out[id][r_gt_0] = nid;
}
if (nid >= (int)next_dp.size()) next_dp.resize(nid + 1, vector<long long>(65, 0));
// Option 2 & 3: Pick a previously unused color, or a color missing from current window
for (int C = 0; C <= i; ++C) {
if (long long val = dp[id][C]) {
if (C > c_prof) {
long long ways = C - c_prof;
next_dp[nid][C] = (next_dp[nid][C] + val * ways) % MOD;
}
if (C + 1 <= 64) {
next_dp[nid][C + 1] = (next_dp[nid][C + 1] + val) % MOD;
}
}
}
}
dp = move(next_dp);
// Record configurations tracking the fully completed NxM grid blocks
if (c == M - 1) {
int N = r + 1;
for (int id = 0; id < (int)dp.size(); ++id) {
for (int C = 1; C <= N * M; ++C) {
W[N][M][C] = (W[N][M][C] + dp[id][C]) % MOD;
}
}
}
}
}
}
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute();
int T;
if (!(cin >> T)) return 0;
while (T--) {
int N, M;
long long K;
cin >> N >> M >> K;
// Ensure bounds scale up to max tracked M
if (N > M) swap(N, M);
long long ans = 0;
long long P = 1;
for (int C = 1; C <= min((long long)N * M, K); ++C) {
P = (P * ((K - C + 1) % MOD)) % MOD;
long long term = (W[N][M][C] * P) % MOD;
ans = (ans + term) % MOD;
}
cout << ans << "\n";
}
return 0;
}
HackerRank Combinatorics – Coloring Grid