NLinker

Задача о замощении домино

May 10th, 2021
724
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// Имеется прямоугольное поле размера `n \times m`. Нужно посчитать число способов замостить его
  2. /// доминошками размера `1 \times 2`. Доминошки могут быть повернуты горизонтально или вертикально,
  3. /// но они не должны перекрываться или выходить за пределы поля. Поскольку ответ может быть
  4. /// достаточно большим, требуется вывести его по модулю `k` (остаток от деления ответа на `k`).
  5. pub fn solve() {
  6.     let m: u32 = 16;
  7.     let n: u32 = 16;
  8.     let bound: u64 = 1_000_000_000;
  9.     let mut d = vec![0u64; 2_u32.pow(m) as usize];
  10.     d[0] = 1;
  11.     // optimized to the left shifts
  12.     let pow2_m2 = 2_u32.pow(m - 2);
  13.     let pow2_m1 = 2_u32.pow(m - 1);
  14.     for _ in 0..n {
  15.         for i in 0..m - 1 {
  16.             for k in 0..pow2_m2 {
  17.                 let k0 = insert_00(i, k);
  18.                 let t = 1 << i;
  19.                 let k1 = k0 + t;
  20.                 let k2 = k1 + t;
  21.                 let k3 = k2 + t;
  22.                 d.swap(k0, k1);
  23.                 d.swap(k2, k3);
  24.                 d[k2] += d[k1];
  25.                 d[k2] %= bound;
  26.             }
  27.         }
  28.         for k in 0..pow2_m1 {
  29.             let k0 = k as usize;
  30.             let k1 = k0 + pow2_m1 as usize;
  31.             d.swap(k0, k1);
  32.         }
  33.     }
  34.     println!("m = {}, n = {}, d = {}", m, n, d[0]);
  35. }
  36.  
  37. /// функция вставляет два нулевых бита в позицию i,
  38. /// пример для k == 63 и i == 0, 1, ... , 6
  39. ///   11111100
  40. ///   11111001
  41. ///   11110011
  42. ///   11100111
  43. ///   11001111
  44. ///   10011111
  45. ///   00111111
  46. fn insert_00(i: u32, k: u32) -> usize {
  47.     let mut x = k.clone();
  48.     let mut y = k.clone();
  49.     x <<= 2;
  50.     x &= (3_u32 << i).not();
  51.     x &= 0_u32.not() << i;
  52.     y &= (0_u32.not() << i).not();
  53.     x |= y;
  54.     x as usize
  55. }
  56.  
RAW Paste Data