学步园

自动机构造矩阵 注意初值与解状态取舍

#include <stdio.h>
#include <iostream>
using namespace std;
const int mod = 34830;
const int maxn = 10;
typedef long long ll;

int n,k;

struct mat
{
  ll e[maxn][maxn];
  int step;
  void init (int flag, int s)
  {
    step = s;
    for (int i = 1; i <= s; i++)
    {
      for (int j = 1; j <= s; j++)
      {
          if (i == j) e[i][j] = flag;
          else e[i][j] = 0;
      }
    }
  }
  void output_mat()
  {
    for (int i = 1; i <= step; i++)
    {
      for (int j = 1; j <= step; j++)
      {
        cout << e[i][j] << " ";
      }
      cout<<endl;
    }
  }
} op;

mat mul (mat a, mat b)
{
  mat ret;
  ret.init (0, a.step);
  for (int i = 1; i <= ret.step; i++)
  {
    for (int j = 1; j <= ret.step; j++)
    {
      if (a.e[i][j])
      {
        for (int k = 1; k <= ret.step; k++)
        {
          ret.e[i][k] += (a.e[i][j] * b.e[j][k]) % mod;
          ret.e[i][k] %= mod;
        }
      }
    }
  }
  return ret;
}
mat qpow (mat a,int p)
{
  mat ret;
  ret.init (1, a.step);
  for (; p; p >>= 1)
  {
    if (p & 1) ret = mul(ret, a);
    a = mul(a, a);
  }
  return ret;
}

void init_op()
{
  op.init(0,7);

  op.e[1][1] = (k - 4) % mod; op.e[1][4] = (k - 3) % mod;
  op.e[1][5] = (k - 3) % mod;

  op.e[2][1] =             1; op.e[2][4] =             1;
  op.e[3][1] =             1; op.e[3][5] =             1;
  op.e[4][3] = (k - 3) % mod; op.e[4][7] = (k - 2) % mod;
  op.e[5][2] = (k - 3) % mod; op.e[5][6] = (k - 2) % mod;
  op.e[6][3] =             1;
  op.e[7][2] =             1;
}

ll fuct (ll x,int t)
{
  ll ans = 1;
  for (int i = 0; i < t; i++)
  {
      ans *= (x - i) % mod;
      ans %= mod;
  }
  return ans;
}

ll meow()
{
  if (n <= 3) return fuct(k, n);
  if (k < 3) return 0;
  init_op();
  op = qpow (op, n - 4);
  ll ans = 0;
  ans = (ans + op.e[1][1] * fuct (k, 4)) % mod;
  ans = (ans + op.e[1][3] * fuct (k, 3)) % mod;
  ans = (ans + op.e[5][1] * fuct (k, 4)) % mod;
  ans = (ans + op.e[5][3] * fuct (k, 3)) % mod;
  return ans;
}

int main()
{
  int n_case;
  scanf ("%d", &n_case);
  for (int i_case = 1; i_case <= n_case; i_case++)
  {
      scanf ("%d%d", &n, &k);
      printf ("Case %d: %lld\n", i_case, meow ());
  }
  return 0;
}