提出 #54929838

---

ソースコード 拡げる

#include <stdio.h>

void mul_matrix (long long **a, long long **b, int l, int m, int n, long long **ans, long long mod_num) {
  for (int i = 0; i < l; i++) {
    for (int j = 0; j < n; j++) {
      ans[i][j] = 0LL;
      for (int k = 0; k < m; k++) {
        ans[i][j] += a[i][k]*b[k][j];
        ans[i][j] %= mod_num;
      }
    }
  }
  return;
}

long long power_mod (long long a, long long b, long long mod_num) {
  long long ans = 1LL;
  
  if (b > 0LL) {
    ans = power_mod(a, b/2LL, mod_num);
    ans = (ans * ans) % mod_num;
    if (b%2LL == 1LL) {
      ans = (ans * a) % mod_num;
    }
  }
  
  return ans;
}

int main () {
  int t = 0;
  long long n = 0LL;
  
  int res = 0;
  
  long long mod_num = 998244353LL;
  
  long long comb[12][12] = {};
  long long s_obj[6][1][13] = {};
  long long *s[6][1] = {};
  long long s_inv_obj[6][13][1] = {};
  long long *s_inv[6][13] = {};
  
  long long cnt[6] = { 2LL, 12LL, 42LL, 112LL, 252LL, 504LL };
  
  long long invf[12] = {};
  
  for (int i = 0; i < 12; i++) {
    comb[i][0] = 1LL;
    comb[i][i] = 1LL;
    for (int j = 1; j < i; j++) {
      comb[i][j] = (comb[i-1][j-1]+comb[i-1][j])%mod_num;
    }
  }
  
  for (int i = 0; i < 6; i++) {
    s[i][0] = s_obj[i][0];
    for (int j = 0; j < 13; j++) {
      s_inv[i][j] = s_inv_obj[i][j];
    }
  }
  
  for (int i = 0; i < 6; i++) {
    s[i][0][0] = 1LL;
    for (int j = 1; j < 6+i; j++) {
      s[i][0][j] = 0LL;
    }
    for (int j = 6+i; j < 12; j++) {
      s[i][0][j] = comb[j-1][j-i-6];
      if ((j-i)%2 == 1) {
        s[i][0][j] = mod_num-s[i][0][j];
      }
    }
    s[i][0][12] = 1LL;
    for (int j = 0; j < 6+i; j++) {
      s_inv[i][j][0] = mod_num-power_mod(2LL, ((long long)(6+i-j))*(mod_num-2LL), mod_num);
      for (int k = 0; k < 6-i; k++) {
        if (k%2 == 0) {
          s_inv[i][j][0] += comb[5+i-j+k][k];
        } else {
          s_inv[i][j][0] += mod_num-comb[5+i-j+k][k];
        }
      }
      s_inv[i][j][0] %= mod_num;
    }
    for (int j = 6+i; j < 12; j++) {
      s_inv[i][j][0] = mod_num-1LL;
    }
    s_inv[i][12][0] = power_mod(2LL, ((long long)(6+i))*(mod_num-2LL), mod_num);
  }
  
  invf[0] = 1LL;
  for (int i = 1; i < 12; i++) {
    invf[i] = invf[i-1]*power_mod((long long)i, mod_num-2LL, mod_num);
    invf[i] %= mod_num;
  }
  
  res = scanf("%d", &t);
  while (t > 0) {
    res = scanf("%lld", &n);
    if (n < 12LL) {
      printf("0\n");
    } else {
      long long ans = 0LL;
      long long perm[13] = {};
      perm[0] = 1LL;
      for (int i = 0; i < 12; i++) {
        perm[i+1] = perm[i]*(n-((long long)i));
        perm[i+1] %= mod_num;
      }
      for (int i = 0; i < 6; i++) {
        long long wk1_obj[13][13] = {};
        long long *wk1[13] = {};
        long long wk2_obj[1][13] = {};
        long long *wk2[1] = { wk2_obj[0] };
        long long wk3_obj[1][1] = {};
        long long *wk3[1] = { wk3_obj[0] };
        long long tmppow = power_mod(50LL, (n-(long long)(i+5)), mod_num);
        for (int j = 0; j < 13; j++) {
          wk1[j] = wk1_obj[j];
        }
        for (int j = i+5; j >= 0; j--) {
          long long tmp = (perm[j]*invf[j])%mod_num;
          tmp *= tmppow;
          tmp %= mod_num;
          for (int k = 0; k < i+6-j; k++) {
            wk1[k][j+k] = tmp;
          }
          tmppow *= 50LL;
          tmppow %= mod_num;
        }
        tmppow = power_mod(51LL, (n-(long long)(5-i)), mod_num);
        for (int j = 5-i; j >= 0; j--) {
          long long tmp = (perm[j]*invf[j])%mod_num;
          tmp *= tmppow;
          tmp %= mod_num;
          for (int k = 0; k < 6-i-j; k++) {
            wk1[k+i+6][j+k+i+6] = tmp;
          }
          tmppow *= 51LL;
          tmppow %= mod_num;
        }
        wk1[12][12] = power_mod(52LL, n, mod_num);
        mul_matrix(s[i], wk1, 1, 13, 13, wk2, mod_num);
        mul_matrix(wk2, s_inv[i], 1, 13, 1, wk3, mod_num);
        ans += cnt[i]*wk3[0][0];
      }
      printf("%lld\n", ans%mod_num);
    }
    t--;
  }
  
  return 0;
}

提出情報

ジャッジ結果