To solve this problem, we need to count the number of valid ways to color a 3×N grid using K colors such that no two adjacent cells (sharing a side) have the same color. The solution leverages dynamic programming (DP) with matrix exponentiation to efficiently handle large values of N.
Approach
-
State Classification:
- Type1: Column state where the top and bottom cells are the same color (e.g., (x, y, x)).
- Type2: Column state where all three cells are distinct (e.g., (x, y, z) with x≠y≠z≠x).
-
State Transitions:
- A: Number of Type1 transitions from Type1.
- B: Number of Type2 transitions from Type1.
- C: Number of Type1 transitions from Type2.
- D: Number of Type2 transitions from Type2.
-
Matrix Exponentiation:
- The transitions can be represented as a 2x2 matrix. For large N, we use matrix exponentiation to compute the result in O(log N) time.
Key Formulas
- Type1 Count: K*(K-1)
- Type2 Count: K(K-1)(K-2)
- Transitions:
- A = K² -3K +3
- B = (K-1)*(K-2)²
- C = K² -4K +5
- D = B (since Type2→Type2 transitions are same as Type1→Type2)
Solution Code
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
struct Matrix {
ll m[2][2];
Matrix() {
m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;
}
};
Matrix multiply(Matrix a, Matrix b) {
Matrix res;
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
for(int k=0; k<2; k++) {
res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
}
}
}
return res;
}
Matrix matrix_pow(Matrix a, ll power) {
Matrix res;
// Identity matrix
res.m[0][0] = res.m[1][1] = 1;
while(power >0) {
if(power%2 == 1) {
res = multiply(res, a);
}
a = multiply(a,a);
power /= 2;
}
return res;
}
int main() {
ll N, K;
cin >> N >> K;
if(N ==1) {
ll ans = K * (K-1) % MOD;
ans = ans * (K-1) % MOD;
cout << ans << endl;
return 0;
}
// Compute transitions
ll A = (K*K -3*K +3) % MOD;
if(A <0) A += MOD;
ll B = ( (K-1) * ( (K-2)*(K-2) % MOD ) ) % MOD;
if(B <0) B += MOD;
ll C = (K*K -4*K +5) % MOD;
if(C <0) C += MOD;
ll D = B;
// Build matrix M
Matrix M;
M.m[0][0] = A;
M.m[0][1] = C;
M.m[1][0] = B;
M.m[1][1] = D;
// Compute M^(N-1)
Matrix M_pow = matrix_pow(M, N-1);
// Initial vector: [Type1, Type2]
ll initial0 = K*(K-1) % MOD;
ll initial1 = (K*(K-1) % MOD) * (K-2) % MOD;
if(initial1 <0) initial1 += MOD;
// Compute final values
ll final0 = (M_pow.m[0][0] * initial0 + M_pow.m[0][1] * initial1) % MOD;
ll final1 = (M_pow.m[1][0] * initial0 + M_pow.m[1][1] * initial1) % MOD;
ll ans = (final0 + final1) % MOD;
cout << ans << endl;
return 0;
}
Explanation
- Matrix Multiplication: Combines two matrices to get the transition matrix for multiple steps.
- Matrix Exponentiation: Efficiently computes the power of the transition matrix to handle large N.
- Initial State: The initial state for N=1 is the count of Type1 and Type2 columns.
- Final Result: The sum of Type1 and Type2 states for N columns gives the total valid colorings.
This approach ensures that we handle large values of N efficiently, making it suitable for constraints where N can be up to 1e9. The solution is computed modulo 1e9+7 to avoid overflow and meet the problem's requirements.


作者声明:本文包含人工智能生成内容。