Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Hardbitmask-dp

Painting a Grid With Three Different Colors

Problem (yeniden ifade)

m × n ızgarayı (m ≤ 5, n ≤ 1000) 3 renkle boya; kenar komşuları farklı olsun. Sayıyı 10^9+7 modunda döndür.

Sezgi

Kısa kenar durumdur. Sütunu 3-tabanlı tamsayı olarak kodla (3^m ≤ 243). Dikey komşuları eşit olmayan boyamaları tut, sonra n sütun boyunca uyumlu çiftlerle (aynı satırda eşit renk yok) DP yap.

Yaklaşımlar

Sütun-durum DP

Doğrulanmadı

Zaman O(n * 3^{2m})Alan O(3^m)

Fikir. Geçerli sütun kodlarını üret. adj[i] = i ile uyumlu kodlar. dp[state] = mevcut sütunu state olarak boyama sayısı. n-1 kez yuvarla. Her eklemede mod.

Yürüyüş. m=1,n=1 → 3. m=1,n=2 → 6. m=5,n=5 → 580986.

Trade-off. Geçerli durumlar 3·2^{m-1} (m=5’te 48), tam 243 değil. C#’ta moddan önce long.

Çözüm

const MOD = 1_000_000_007;

export function colorTheGrid(m: number, n: number): number {
  const states: number[] = [];
  const gen = (pos: number, prev: number, enc: number): void => {
    if (pos === m) {
      states.push(enc);
      return;
    }
    for (let c = 0; c < 3; c++) {
      if (c !== prev) gen(pos + 1, c, enc * 3 + c);
    }
  };
  gen(0, -1, 0);
  const S = states.length;
  const compat = (a: number, b: number): boolean => {
    for (let i = 0; i < m; i++) {
      if (a % 3 === b % 3) return false;
      a = Math.floor(a / 3);
      b = Math.floor(b / 3);
    }
    return true;
  };
  const adj: number[][] = Array.from({ length: S }, () => []);
  for (let i = 0; i < S; i++) {
    for (let j = 0; j < S; j++) {
      if (compat(states[i]!, states[j]!)) adj[i]!.push(j);
    }
  }
  let dp = new Array<number>(S).fill(1);
  for (let col = 1; col < n; col++) {
    const ndp = new Array<number>(S).fill(0);
    for (let i = 0; i < S; i++) {
      const w = dp[i]!;
      if (!w) continue;
      for (const j of adj[i]!) ndp[j] = (ndp[j]! + w) % MOD;
    }
    dp = ndp;
  }
  let ans = 0;
  for (const v of dp) ans = (ans + v) % MOD;
  return ans;
}

const MOD = 1_000_000_007;

export function colorTheGrid(m: number, n: number): number {
  const states: number[] = [];
  const gen = (pos: number, prev: number, enc: number): void => {
    if (pos === m) {
      states.push(enc);
      return;
    }
    for (let c = 0; c < 3; c++) {
      if (c !== prev) gen(pos + 1, c, enc * 3 + c);
    }
  };
  gen(0, -1, 0);
  const S = states.length;
  const compat = (a: number, b: number): boolean => {
    for (let i = 0; i < m; i++) {
      if (a % 3 === b % 3) return false;
      a = Math.floor(a / 3);
      b = Math.floor(b / 3);
    }
    return true;
  };
  const adj: number[][] = Array.from({ length: S }, () => []);
  for (let i = 0; i < S; i++) {
    for (let j = 0; j < S; j++) {
      if (compat(states[i]!, states[j]!)) adj[i]!.push(j);
    }
  }
  let dp = new Array<number>(S).fill(1);
  for (let col = 1; col < n; col++) {
    const ndp = new Array<number>(S).fill(0);
    for (let i = 0; i < S; i++) {
      const w = dp[i]!;
      if (!w) continue;
      for (const j of adj[i]!) ndp[j] = (ndp[j]! + w) % MOD;
    }
    dp = ndp;
  }
  let ans = 0;
  for (const v of dp) ans = (ans + v) % MOD;
  return ans;
}

Şablon bağlantısı

Renklendirme bitmask DP: maske tüm sütun (3-taban, bit değil), ekstra boyut önceki sütun, geçişler uyumlu liste.

Yansıma

Geçerli sütun kodu: komşu satırlar farklı renk. dp o sütunun boyanma sayısı. Uyumlu kodlar arasında n−1 geçiş.
Her geçişte mod. m ≤ 5, renk 3, sütun kodu sayısı 3^m’i aşmaz.
n = 1 yalnız sütun içi. m = 1 ise komşu sütunlar farklı renk.