GP of Dolgoprudny Automaton

sam.cpp

#include <bits/stdc++.h>

const int N = 40;

const int MOD = 1e9 + 7;

using Mask = uint64_t;

void update(int &x, int a) {
  x += a;
  if (x >= MOD) {
    x -= MOD;
  }
}

int parent[N];

int find(int u) {
  if (!~parent[u]) {
    return u;
  }
  return parent[u] = find(parent[u]);
}

void merge(int a, int b) {
  if (find(a) != find(b)) {
    parent[find(a)] = find(b);
  }
}

void prepare(Mask mask, int n, int maxp) {
  for (int p = 1; p <= maxp; ++p) {
    if (mask >> p & 1) {
      for (int i = p; i < n; ++i) {
        merge(i - p, i);
      }
    }
  }
}

struct Period {
  Period(int n) : n(n) {
    dfs(1, 0, 0);
    std::sort(masks.begin(), masks.end());
  }

  void dfs(int p, Mask m1, Mask m2) {
    if (p < n) {
      if (check(m1, m2, p)) {
        dfs(p + 1, m1, m2);
      }
      if (p < n - 1) {
        m1 |= static_cast<Mask>(1) << p;
        if (check(m1, m2, p)) {
          dfs(p + 1, m1, m2);
        }
      }
      m2 |= static_cast<Mask>(1) << p;
      if (check(m1, m2, p)) {
        dfs(p + 1, m1, m2);
      }
    } else {
      masks.emplace_back(m1, m2);
    }
  }

  bool check(Mask m1, Mask m2, int maxp) {
    // m1 = n - 1, m2 = n
    memset(parent, -1, sizeof(parent));
    prepare(m1, n - 1, maxp);
    prepare(m2, n, maxp);
    for (int p = 1; p <= maxp; ++p) {
      bool valid = true;
      for (int i = p; i < n - 1 && valid; ++i) {
        valid &= find(i - p) == find(i);
      }
      if (p < n - 1 && valid && (~m1 >> p & 1)) {
        return false;
      }
      valid &= find(n - 1 - p) == find(n - 1);
      if (valid && (~m2 >> p & 1)) {
        return false;
      }
    }
    return true;
  }

  int n;
  std::vector<std::tuple<Mask, Mask>> masks;
};

struct PreparedMask {
  Mask m1, m2;
  int count;
  std::vector<int> supers;
};

int power[N + 1], result[N + 1][N + 1], dp[N + 1];
std::vector<PreparedMask> pmasks[N + 1];

int main() {
  for (int len = 1; len <= N; ++len) {
    auto masks = Period(len).masks;
    int n = masks.size();
    for (int i = 0; i < n; ++i) {
      memset(parent, -1, sizeof(parent));
      prepare(std::get<0>(masks[i]), len - 1, len - 2);
      prepare(std::get<1>(masks[i]), len, len - 1);
      int count = 0;
      for (int j = 0; j < len; ++j) {
        count += find(j) == j;
      }
      std::vector<int> supers;
      for (int j = i + 1; j < n; ++j) {
        if ((std::get<0>(masks[i]) & std::get<0>(masks[j])) ==
                std::get<0>(masks[i]) &&
            (std::get<1>(masks[i]) & std::get<1>(masks[j])) ==
                std::get<1>(masks[i])) {
          supers.push_back(j);
        }
      }
      pmasks[len].push_back(
          {std::get<0>(masks[i]), std::get<1>(masks[i]), count, supers});
    }
  }
  for (int k = 1; k <= N; ++k) {
    power[0] = 1;
    for (int i = 1; i <= N; ++i) {
      power[i] = 1LL * power[i - 1] * k % MOD;
      result[k][i] = power[i] % MOD;
    }
    for (int len = 1; len <= N; ++len) {
      std::vector<int> ways(pmasks[len].size());
      for (int i = static_cast<int>(ways.size()) - 1; i >= 0; --i) {
        ways[i] = power[pmasks[len][i].count];
        for (int j : pmasks[len][i].supers) {
          update(ways[i], MOD - ways[j]);
        }
      }
      for (int t = 0; t < static_cast<int>(ways.size()); ++t) {
        Mask mask = pmasks[len][t].m2;
        memset(dp, 0, sizeof(dp));
        int sum = 0;
        for (int i = len; i <= N; ++i) {
          dp[i] = power[i - len];
          for (int j = len; j < i; ++j) {
            if (i - j >= len) {
              update(dp[i], 1LL * (MOD - dp[j]) * power[i - j - len] % MOD);
            } else if (mask >> (i - j) & 1) {
              update(dp[i], MOD - dp[j]);
            }
          }
          sum = (1LL * sum * k % MOD + 1LL * dp[i] * ways[t]) % MOD;
          update(result[k][i], sum);
        }
      }
      if (len > 1) {
        for (int t = 0; t < static_cast<int>(ways.size()); ++t) {
          Mask mask = pmasks[len][t].m1;
          memset(dp, 0, sizeof(dp));
          int sum = 0;
          for (int i = len - 1; i <= N; ++i) {
            dp[i] = MOD - power[i - (len - 1)];
            for (int j = len - 1; j < i; ++j) {
              if (i - j >= len - 1) {
                update(dp[i],
                       1LL * (MOD - dp[j]) * power[i - j - (len - 1)] % MOD);
              } else if (mask >> (i - j) & 1) {
                update(dp[i], MOD - dp[j]);
              }
            }
            sum = (1LL * sum * k % MOD + 1LL * dp[i] * ways[t]) % MOD;
            if (len <= i) {
              update(result[k][i], sum);
            }
          }
          Mask m1 = pmasks[len][t].m1;
          Mask m2 = pmasks[len][t].m2;
          sum = 0;
          for (int i = len - 1; i <= N; ++i) {
            dp[i] = power[i - (len - 1)];
            if (i >= len) {
              update(dp[i], MOD - power[i - len]);
            }
            for (int j = len - 1; j < i; ++j) {
              if (i - j >= len - 1) {
                update(dp[i],
                       1LL * (MOD - dp[j]) * power[i - j - (len - 1)] % MOD);
                if (i - j >= len) {
                  update(dp[i], 1LL * dp[j] * power[i - j - len] % MOD);
                } else if (m2 >> (i - j) & 1) {
                  update(dp[i], dp[j]);
                }
              } else if (m1 >> (i - j) & 1) {
                update(dp[i], MOD - dp[j]);
                if (m2 >> (i - j) & 1) {
                  update(dp[i], dp[j]);
                }
              }
            }
            sum = (1LL * sum * k % MOD + 1LL * dp[i] * ways[t]) % MOD;
            if (len <= i) {
              update(result[k][i], sum);
            }
          }
        }
      }
    }
  }
  int T;
  std::cin >> T;
  while (T--) {
    int n, k;
    std::cin >> n >> k;
    std::cout << result[k][n] << std::endl;
  }
}