#901291 (Java21) No.2413 Multiple of 99

提出ソース

結果

問題	No.2413 Multiple of 99
ユーザー	hiromi_ayase
提出日時	2023-08-12 05:22:35
言語	Java21 (openjdk 21)
結果	AC
実行時間	5,401 ms / 8,000 ms
コード長	9,173 bytes
コンパイル時間	2,634 ms
コンパイル使用メモリ	89,452 KB
実行使用メモリ	150,688 KB
最終ジャッジ日時	2024-04-29 19:56:27
合計ジャッジ時間	62,981 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	52 ms 37,576 KB
testcase_01	AC	49 ms 36,972 KB
testcase_02	AC	55 ms 37,752 KB
testcase_03	AC	50 ms 37,328 KB
testcase_04	AC	234 ms 46,352 KB
testcase_05	AC	387 ms 50,216 KB
testcase_06	AC	350 ms 48,208 KB
testcase_07	AC	5,226 ms 150,552 KB
testcase_08	AC	53 ms 37,704 KB
testcase_09	AC	5,166 ms 150,548 KB
testcase_10	AC	5,007 ms 150,688 KB
testcase_11	AC	5,401 ms 150,536 KB
testcase_12	AC	4,982 ms 150,536 KB
testcase_13	AC	4,955 ms 150,600 KB
testcase_14	AC	4,896 ms 150,536 KB
testcase_15	AC	4,953 ms 150,676 KB
testcase_16	AC	2,555 ms 97,320 KB
testcase_17	AC	2,581 ms 95,452 KB
testcase_18	AC	5,174 ms 134,448 KB
testcase_19	AC	479 ms 48,420 KB
testcase_20	AC	360 ms 49,380 KB
testcase_21	AC	478 ms 48,164 KB
testcase_22	AC	5,034 ms 134,716 KB
testcase_23	AC	783 ms 59,528 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.util.*;
import java.util.function.BiFunction;
import java.io.*;

@SuppressWarnings("unused")
public class Main {

  private static class Convolution {
    /**
     * Find a primitive root.
     *
     * @param m A prime number.
     * @return Primitive root.
     */
    private static int primitiveRoot() {
      return 3;
    }

    /**
     * Power.
     *
     * @param x Parameter x.
     * @param n Parameter n.
     * @param m Mod.
     * @return n-th power of x mod m.
     */
    private static long pow(long x, long n, int m) {
      if (m == 1)
        return 0;
      long r = 1;
      long y = x % m;
      while (n > 0) {
        if ((n & 1) != 0)
          r = (r * y) % m;
        y = (y * y) % m;
        n >>= 1;
      }
      return r;
    }

    /**
     * Ceil of power 2.
     *
     * @param n Value.
     * @return Ceil of power 2.
     */
    private static int ceilPow2(int n) {
      int x = 0;
      while ((1L << x) < n)
        x++;
      return x;
    }

    /**
     * Garner's algorithm.
     *
     * @param c    Mod convolution results.
     * @param mods Mods.
     * @return Result.
     */
    private static long garner(long[] c, int[] mods) {
      int n = c.length + 1;
      long[] cnst = new long[n];
      long[] coef = new long[n];
      java.util.Arrays.fill(coef, 1);
      for (int i = 0; i < n - 1; i++) {
        int m1 = mods[i];
        long v = (c[i] - cnst[i] + m1) % m1;
        v = v * pow(coef[i], m1 - 2, m1) % m1;

        for (int j = i + 1; j < n; j++) {
          long m2 = mods[j];
          cnst[j] = (cnst[j] + coef[j] * v) % m2;
          coef[j] = (coef[j] * m1) % m2;
        }
      }
      return cnst[n - 1];
    }

    /**
     * Pre-calculation for NTT.
     *
     * @param mod NTT Prime.
     * @param g   Primitive root of mod.
     * @return Pre-calculation table.
     */
    private static long[] sumE( int g) {
      long[] sum_e = new long[30];
      long[] es = new long[30];
      long[] ies = new long[30];
      int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
      long e = pow(g, (mod - 1) >> cnt2, mod);
      long ie = pow(e, mod - 2, mod);
      for (int i = cnt2; i >= 2; i--) {
        es[i - 2] = e;
        ies[i - 2] = ie;
        e = e * e % mod;
        ie = ie * ie % mod;
      }
      long now = 1;
      for (int i = 0; i < cnt2 - 2; i++) {
        sum_e[i] = es[i] * now % mod;
        now = now * ies[i] % mod;
      }
      return sum_e;
    }

    /**
     * Pre-calculation for inverse NTT.
     *
     * @param mod Mod.
     * @param g   Primitive root of mod.
     * @return Pre-calculation table.
     */
    private static long[] sumIE( int g) {
      long[] sum_ie = new long[30];
      long[] es = new long[30];
      long[] ies = new long[30];

      int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
      long e = pow(g, (mod - 1) >> cnt2, mod);
      long ie = pow(e, mod - 2, mod);
      for (int i = cnt2; i >= 2; i--) {
        es[i - 2] = e;
        ies[i - 2] = ie;
        e = e * e % mod;
        ie = ie * ie % mod;
      }
      long now = 1;
      for (int i = 0; i < cnt2 - 2; i++) {
        sum_ie[i] = ies[i] * now % mod;
        now = now * es[i] % mod;
      }
      return sum_ie;
    }

    /**
     * Inverse NTT.
     *
     * @param a     Target array.
     * @param sumIE Pre-calculation table.
     * @param mod   NTT Prime.
     */
    private static void butterflyInv(long[] a, long[] sumIE) {
      int n = a.length;
      int h = ceilPow2(n);

      for (int ph = h; ph >= 1; ph--) {
        int w = 1 << (ph - 1), p = 1 << (h - ph);
        long inow = 1;
        for (int s = 0; s < w; s++) {
          int offset = s << (h - ph + 1);
          for (int i = 0; i < p; i++) {
            long l = a[i + offset];
            long r = a[i + offset + p];
            a[i + offset] = (l + r) % mod;
            a[i + offset + p] = (mod + l - r) * inow % mod;
          }
          int x = Integer.numberOfTrailingZeros(~s);
          inow = inow * sumIE[x] % mod;
        }
      }
    }

    /**
     * Inverse NTT.
     *
     * @param a    Target array.
     * @param sumE Pre-calculation table.
     * @param mod  NTT Prime.
     */
    private static void butterfly(long[] a, long[] sumE) {
      int n = a.length;
      int h = ceilPow2(n);

      for (int ph = 1; ph <= h; ph++) {
        int w = 1 << (ph - 1), p = 1 << (h - ph);
        long now = 1;
        for (int s = 0; s < w; s++) {
          int offset = s << (h - ph + 1);
          for (int i = 0; i < p; i++) {
            long l = a[i + offset];
            long r = a[i + offset + p] * now % mod;
            a[i + offset] = (l + r) % mod;
            a[i + offset + p] = (l - r + mod) % mod;
          }
          int x = Integer.numberOfTrailingZeros(~s);
          now = now * sumE[x] % mod;
        }
      }
    }

    /**
     * Convolution.
     *
     * @param a   Target array 1.
     * @param b   Target array 2.
     * @param mod NTT Prime.
     * @return Answer.
     */
    public static long[] convolution(long[] a, long[] b) {
      int n = a.length;
      int m = b.length;
      if (n == 0 || m == 0)
        return new long[0];

      int z = 1 << ceilPow2(n + m - 1);
      {
        long[] na = new long[z];
        long[] nb = new long[z];
        System.arraycopy(a, 0, na, 0, n);
        System.arraycopy(b, 0, nb, 0, m);
        a = na;
        b = nb;
      }

      int g = primitiveRoot();
      long[] sume = sumE(g);
      long[] sumie = sumIE( g);

      butterfly(a, sume);
      butterfly(b, sume);
      for (int i = 0; i < z; i++) {
        a[i] = a[i] * b[i] % mod;
      }
      butterflyInv(a, sumie);
      a = java.util.Arrays.copyOf(a, n + m - 1);

      long iz = pow(z, mod - 2, mod);
      for (int i = 0; i < n + m - 1; i++)
        a[i] = a[i] * iz % mod;
      return a;
    }
  }

  private static void solve() {
    int n = ni();
    int k = ni();

    long[] a = new long[10];
    Arrays.fill(a, 1);

    var e = powPloy(a, n/2, mod);
    var o = Arrays.copyOf(e, e.length);
    if (n % 2 == 1) {
      o = Convolution.convolution(a, o);
    }

    int max = n * 9 + 1;

    long[] ret = new long[max];
    long[] co = new long[max];
    long[] ce = new long[max];
  for (int i = 0; i < 11; i++) {

      for (int j = 0; j < max; j++) {
        if (j % 11 != i) {
          co[j] = 0;
          ce[j] = 0;
        } else {
          co[j] = j < o.length ? o[j] : 0;
          ce[j] = j < e.length ? e[j] : 0;
        }
      }
      long[] cur = Convolution.convolution(co, ce);
      for (int j = 0; j < max; j ++) {
        ret[j] = (ret[j] + cur[j]) % mod;
      }
    }

    long ans = 0;
    for (int i = 0; i <= n * 9; i += 9) {
      ans += pow(i, k, mod) * ret[i];
      ans %= mod;
    }
    System.out.println(ans);
  }

  public static long[] powPloy(long[] a, long n, long mod) {
    if (n == 0) {
      return new long[]{1};
    } else if (n % 2 == 1) {
      long[] b = powPloy(a, n / 2, mod);
      long[] v = Convolution.convolution(b, b);
      return Convolution.convolution(v, a);
    } else {
      long[] b = powPloy(a, n / 2, mod);
      return Convolution.convolution(b, b);
    }
  }

  public static long pow(long x, long n, long m){
      assert(n >= 0 && m >= 1);
      long ans = 1;
      while(n > 0){
          if(n%2==1) ans = (ans * x) % m;
          x = (x*x) % m;
          n /= 2;
      }
      return ans;
  }

  private static final int mod = 998244353;


  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        solve();
        out.flush();
      }
    }, "", 64000000).start();
  }

  private static PrintWriter out = new PrintWriter(System.out);
  private static StringTokenizer tokenizer = null;
  private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 32768);

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }
}

yukicoder

結果

テストケース

ソースコード