結果
| 問題 | No.41 貯金箱の溜息（EASY） |
| ユーザー |
 suisen
|
| 提出日時 | 2021-03-27 03:17:32 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 25,533 bytes |
| コンパイル時間 | 4,070 ms |
| コンパイル使用メモリ | 98,192 KB |
| 実行使用メモリ | 37,408 KB |
| 最終ジャッジ日時 | 2024-11-29 07:09:58 |
| 合計ジャッジ時間 | 4,362 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 2 |
ソースコード
import java.io.EOFException;import java.io.File;import java.io.FileDescriptor;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.IOException;import java.io.InputStream;import java.io.OutputStream;import java.io.UncheckedIOException;import java.lang.reflect.Field;import java.nio.CharBuffer;import java.nio.charset.CharacterCodingException;import java.nio.charset.CharsetEncoder;import java.nio.charset.StandardCharsets;import java.util.Arrays;import java.util.OptionalLong;import java.util.function.IntUnaryOperator;import java.util.function.LongUnaryOperator;public class Main {public static void main(String[] args) throws Exception {ExtendedScanner sc = new ExtendedScanner();FastPrintStream pw = new FastPrintStream();solve(sc, pw);sc.close();pw.flush();pw.close();}static final class ModArithmetic1000000009 extends ModArithmetic {public static final ModArithmetic INSTANCE = new ModArithmetic1000000009();private ModArithmetic1000000009(){}public static final long MOD = 1000000009;public long getMod() {return MOD;}public long mod(long a) {return (a %= MOD) < 0 ? a + MOD : a;}public long add(long a, long b) {return (a += b) >= MOD ? a - MOD : a;}public long sub(long a, long b) {return (a -= b) < 0 ? a + MOD : a;}public long mul(long a, long b) {return (a * b) % MOD;}}static final ModArithmetic ma = ModArithmetic1000000009.INSTANCE;static final int MAX = 100000;public static void solve(ExtendedScanner sc, FastPrintStream pw) {long[] f = new long[MAX + 1];Arrays.fill(f, 1);for (int i = 1; i <= 9; i++) {for (int j = i; j <= MAX; j++) {f[j] = ma.add(f[j], f[j - i]);}}int t = sc.nextInt();while (t --> 0) {int m = (int) (sc.nextLong() / 111111);pw.println(f[m]);}}}/*** @author https://atcoder.jp/users/suisen*/final class ExtendedScanner extends FastScanner {public ExtendedScanner() {super();}public ExtendedScanner(InputStream in) {super(in);}public int[] ints(final int n) {final int[] a = new int[n];Arrays.setAll(a, $ -> nextInt());return a;}public int[] ints(final int n, final IntUnaryOperator f) {final int[] a = new int[n];Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));return a;}public int[][] ints(final int n, final int m) {final int[][] a = new int[n][];Arrays.setAll(a, $ -> ints(m));return a;}public int[][] ints(final int n, final int m, final IntUnaryOperator f) {final int[][] a = new int[n][];Arrays.setAll(a, $ -> ints(m, f));return a;}public long[] longs(final int n) {final long[] a = new long[n];Arrays.setAll(a, $ -> nextLong());return a;}public long[] longs(final int n, final LongUnaryOperator f) {final long[] a = new long[n];Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));return a;}public long[][] longs(final int n, final int m) {final long[][] a = new long[n][];Arrays.setAll(a, $ -> longs(m));return a;}public long[][] longs(final int n, final int m, final LongUnaryOperator f) {final long[][] a = new long[n][];Arrays.setAll(a, $ -> longs(m, f));return a;}public char[][] charArrays(final int n) {final char[][] c = new char[n][];Arrays.setAll(c, $ -> nextChars());return c;}public double[] doubles(final int n) {final double[] a = new double[n];Arrays.setAll(a, $ -> nextDouble());return a;}public double[][] doubles(final int n, final int m) {final double[][] a = new double[n][];Arrays.setAll(a, $ -> doubles(m));return a;}public String[] strings(final int n) {final String[] s = new String[n];Arrays.setAll(s, $ -> next());return s;}}/*** @author https://atcoder.jp/users/suisen*/class FastPrintStream implements AutoCloseable {private static final int INT_MAX_LEN = 11;private static final int LONG_MAX_LEN = 20;private int precision = 9;private static final int BUF_SIZE = 1 << 14;private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;private final byte[] buf = new byte[BUF_SIZE];private int ptr = 0;private final Field strField;private final CharsetEncoder encoder;private final OutputStream out;public FastPrintStream(OutputStream out) {this.out = out;Field f;try {f = String.class.getDeclaredField("value");f.setAccessible(true);} catch (NoSuchFieldException | SecurityException e) {f = null;}this.strField = f;this.encoder = StandardCharsets.US_ASCII.newEncoder();}public FastPrintStream(File file) throws IOException {this(new FileOutputStream(file));}public FastPrintStream(String filename) throws IOException {this(new File(filename));}public FastPrintStream() {this(new FileOutputStream(FileDescriptor.out));}public FastPrintStream println() {if (ptr == BUF_SIZE) internalFlush();buf[ptr++] = (byte) '\n';return this;}public FastPrintStream println(Object o) {return print(o).println();}public FastPrintStream println(String s) {return print(s).println();}public FastPrintStream println(char[] s) {return print(s).println();}public FastPrintStream println(char c) {return print(c).println();}public FastPrintStream println(int x) {return print(x).println();}public FastPrintStream println(long x) {return print(x).println();}public FastPrintStream println(double d, int precision) {return print(d, precision).println();}public FastPrintStream println(double d) {return print(d).println();}private FastPrintStream print(byte[] bytes) {int n = bytes.length;if (ptr + n > BUF_SIZE) {internalFlush();try {out.write(bytes);} catch (IOException e) {throw new UncheckedIOException(e);}} else {System.arraycopy(bytes, 0, buf, ptr, n);ptr += n;}return this;}public FastPrintStream print(Object o) {return print(o.toString());}public FastPrintStream print(String s) {if (strField == null) {return print(s.getBytes());} else {try {Object value = strField.get(s);if (value instanceof byte[]) {return print((byte[]) value);} else {return print((char[]) value);}} catch (IllegalAccessException e) {return print(s.getBytes());}}}public FastPrintStream print(char[] s) {try {return print(encoder.encode(CharBuffer.wrap(s)).array());} catch (CharacterCodingException e) {byte[] bytes = new byte[s.length];for (int i = 0; i < s.length; i++) {bytes[i] = (byte) s[i];}return print(bytes);}}public FastPrintStream print(char c) {if (ptr == BUF_SIZE) internalFlush();buf[ptr++] = (byte) c;return this;}public FastPrintStream print(int x) {if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();if (-10 < x && x < 10) {if (x < 0) {buf[ptr++] = '-';x = -x;}buf[ptr++] = (byte) ('0' + x);return this;}int d;if (x < 0) {if (x == Integer.MIN_VALUE) {buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';return this;}d = len(x = -x);buf[ptr++] = '-';} else {d = len(x);}int j = ptr += d;while (x > 0) {buf[--j] = (byte) ('0' + (x % 10));x /= 10;}return this;}public FastPrintStream print(long x) {if ((int) x == x) return print((int) x);if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();int d;if (x < 0) {if (x == Long.MIN_VALUE) {buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';return this;}d = len(x = -x);buf[ptr++] = '-';} else {d = len(x);}int j = ptr += d;while (x > 0) {buf[--j] = (byte) ('0' + (x % 10));x /= 10;}return this;}public FastPrintStream print(double d, int precision) {if (d < 0) {print('-');d = -d;}d += Math.pow(10, -precision) / 2;print((long) d).print('.');d -= (long) d;for(int i = 0; i < precision; i++){d *= 10;print((int) d);d -= (int) d;}return this;}public FastPrintStream print(double d) {return print(d, precision);}public void setPrecision(int precision) {this.precision = precision;}private void internalFlush() {try {out.write(buf, 0, ptr);ptr = 0;} catch (IOException e) {throw new UncheckedIOException(e);}}public void flush() {try {out.write(buf, 0, ptr);out.flush();ptr = 0;} catch (IOException e) {throw new UncheckedIOException(e);}}public void close() {try {out.close();} catch (IOException e) {throw new UncheckedIOException(e);}}private static int len(int x) {returnx >= 1000000000 ? 10 :x >= 100000000 ? 9 :x >= 10000000 ? 8 :x >= 1000000 ? 7 :x >= 100000 ? 6 :x >= 10000 ? 5 :x >= 1000 ? 4 :x >= 100 ? 3 :x >= 10 ? 2 : 1;}private static int len(long x) {returnx >= 1000000000000000000L ? 19 :x >= 100000000000000000L ? 18 :x >= 10000000000000000L ? 17 :x >= 1000000000000000L ? 16 :x >= 100000000000000L ? 15 :x >= 10000000000000L ? 14 :x >= 1000000000000L ? 13 :x >= 100000000000L ? 12 :x >= 10000000000L ? 11 : 10;}}/*** @author https://atcoder.jp/users/suisen*/class FastScanner implements AutoCloseable {private final ByteBuffer tokenBuf = new ByteBuffer();public final InputStream in;private final byte[] rawBuf = new byte[1 << 14];private int ptr = 0;private int buflen = 0;public FastScanner(InputStream in) {this.in = in;}public FastScanner() {this(new FileInputStream(FileDescriptor.in));}private int readByte() {if (ptr < buflen) return rawBuf[ptr++];ptr = 0;try {buflen = in.read(rawBuf);if (buflen > 0) {return rawBuf[ptr++];} else {throw new EOFException();}} catch (IOException e) {throw new UncheckedIOException(e);}}private int readByteUnsafe() {if (ptr < buflen) return rawBuf[ptr++];ptr = 0;try {buflen = in.read(rawBuf);if (buflen > 0) {return rawBuf[ptr++];} else {return -1;}} catch (IOException e) {throw new UncheckedIOException(e);}}private int skipUnprintableChars() {int b = readByte();while (b <= 32 || b >= 127) b = readByte();return b;}private void loadToken() {tokenBuf.clear();for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {tokenBuf.append(b);}}public final boolean hasNext() {for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {if (b == -1) return false;}--ptr;return true;}public final String next() {loadToken();return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());}public final String nextLine() {tokenBuf.clear();for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {if (b == -1) break;tokenBuf.append(b);}return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());}public final char nextChar() {return (char) skipUnprintableChars();}public final char[] nextChars() {loadToken();return tokenBuf.toCharArray();}public final long nextLong() {long n = 0;boolean isNegative = false;int b = skipUnprintableChars();if (b == '-') {isNegative = true;b = readByteUnsafe();}if (b < '0' || '9' < b) throw new NumberFormatException();while ('0' <= b && b <= '9') {// -9223372036854775808 - 9223372036854775807if (n >= 922337203685477580L) {if (n > 922337203685477580L) {throw new ArithmeticException("long overflow");}if (isNegative) {if (b >= '9') {throw new ArithmeticException("long overflow");}n = -n - (b - '0');} else {if (b >= '8') {throw new ArithmeticException("long overflow");}n = n * 10 + b - '0';}b = readByteUnsafe();if ('0' <= b && b <= '9') {throw new ArithmeticException("long overflow");} else if (b <= 32 || b >= 127) {return n;} else {throw new NumberFormatException();}}n = n * 10 + b - '0';b = readByteUnsafe();}if (b <= 32 || b >= 127) return isNegative ? -n : n;throw new NumberFormatException();}public final int nextInt() {long value = nextLong();if ((int) value != value) {throw new ArithmeticException("int overflow");}return (int) value;}public final double nextDouble() {return Double.parseDouble(next());}public final void close() {try {in.close();} catch (IOException e) {throw new UncheckedIOException(e);}}@SuppressWarnings("UnusedReturnValue")private static final class ByteBuffer {private static final int DEFAULT_BUF_SIZE = 1 << 12;private byte[] buf;private int ptr = 0;private ByteBuffer(@SuppressWarnings("SameParameterValue") int capacity) {this.buf = new byte[capacity];}private ByteBuffer() {this(DEFAULT_BUF_SIZE);}private ByteBuffer append(int b) {if (ptr == buf.length) {int newLength = buf.length << 1;byte[] newBuf = new byte[newLength];System.arraycopy(buf, 0, newBuf, 0, buf.length);buf = newBuf;}buf[ptr++] = (byte) b;return this;}private char[] toCharArray() {char[] chs = new char[ptr];for (int i = 0; i < ptr; i++) {chs[i] = (char) buf[i];}return chs;}private byte[] getRawBuf() {return buf;}private int size() {return ptr;}private void clear() {ptr = 0;}}}/*** @author https://atcoder.jp/users/suisen*/abstract class ModArithmetic {public abstract long getMod();public abstract long mod(long a);public abstract long add(long a, long b);public abstract long sub(long a, long b);public abstract long mul(long a, long b);public final long div(long a, long b) {return mul(a, inv(b));}public final long inv(long a) {a = mod(a);long b = getMod();long u = 1, v = 0;while (b >= 1) {long t = a / b;a -= t * b;long tmp1 = a; a = b; b = tmp1;u -= t * v;long tmp2 = u; u = v; v = tmp2;}if (a != 1) throw new ArithmeticException("divide by zero");return mod(u);}public final long fma(long a, long b, long c) {return add(mul(a, b), c);}public final long pow(long a, long b) {long pow = 1;for (a = mod(a); b > 0; b >>= 1, a = mul(a, a)) {if ((b & 1) == 1) pow = mul(pow, a);}return pow;}public final long add(long a, long b, long c) {return mod(a + b + c);}public final long add(long a, long b, long c, long d) {return mod(a + b + c + d);}public final long add(long a, long b, long c, long d, long e) {return mod(a + b + c + d + e);}public final long add(long a, long b, long c, long d, long e, long f) {return mod(a + b + c + d + e + f);}public final long add(long a, long b, long c, long d, long e, long f, long g) {return mod(a + b + c + d + e + f + g);}public final long add(long a, long b, long c, long d, long e, long f, long g, long h) {return mod(a + b + c + d + e + f + g + h);}public final long add(long... xs) {long s = 0; for (long x : xs) s += x; return mod(s);}public final long mul(long a, long b, long c) {return mul(a, mul(b, c));}public final long mul(long a, long b, long c, long d) {return mul(a, mul(b, mul(c, d)));}public final long mul(long a, long b, long c, long d, long e) {return mul(a, mul(b, mul(c, mul(d, e))));}public final long mul(long a, long b, long c, long d, long e, long f) {return mul(a, mul(b, mul(c, mul(d, mul(e, f)))));}public final long mul(long a, long b, long c, long d, long e, long f, long g) {return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, g))))));}public final long mul(long a, long b, long c, long d, long e, long f, long g, long h) {return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, mul(g, h)))))));}public final long mul(long... xs) {long s = 1; for (long x : xs) s = mul(s, x); return s;}/*** @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g*/public final long[] gcdInv(long a) {final long m = getMod();a = mod(a);if (a == 0) return new long[]{m, 0};long s = m, t = a;long m0 = 0, m1 = 1;while (t > 0) {long u = s / t;s -= t * u;m0 -= m1 * u;long tmp;tmp = s; s = t; t = tmp;tmp = m0; m0 = m1; m1 = tmp;}if (m0 < 0) m0 += m / s;return new long[]{s, m0};}public final OptionalLong sqrt(long a) {a = mod(a);if (a == 0) return OptionalLong.of(0);if (a == 1) return OptionalLong.of(1);long p = getMod();if (pow(a, (p - 1) >> 1) != 1) {return OptionalLong.empty();}if ((p & 3) == 3) {return OptionalLong.of(pow(a, (p + 1) >> 2));}if ((p & 7) == 5) {if (pow(a, (p - 1) >> 2) == 1) {return OptionalLong.of(pow(a, (p + 3) >> 3));} else {return OptionalLong.of(mul(pow(2, (p - 1) >> 2), pow(a, (p + 3) >> 3)));}}long S = 0, Q = p - 1;while ((Q & 1) == 0) {++S;Q >>= 1;}long z = 1;while (pow(z, (p - 1) >> 1) != p - 1) ++z;long c = pow(z, Q), R = pow(a, (Q + 1) / 2), t = pow(a, Q), M = S;while (t != 1) {long cur = t;int i;for (i = 1; i < M; i++) {cur = mul(cur, cur);if (cur == 1) break;}long b = pow(c, 1L << (M - i - 1));c = mul(b, b); R = mul(R, b); t = mul(t, b, b); M = i;}return OptionalLong.of(R);}public final int primitiveRoot() {final int m = Math.toIntExact(getMod());if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;int[] divs = new int[20];divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long) i * i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) x /= i;}}if (x > 1) {divs[cnt++] = x;}for (int g = 2; ; g++) {boolean ok = true;for (int i = 0; i < cnt; i++) {if (pow(g, (m - 1) / divs[i]) == 1) {ok = false;break;}}if (ok) return g;}}/** array operations */public final long[] rangeInv(int n) {final long MOD = getMod();long[] invs = new long[n + 1];if (n == 0) return invs;invs[1] = 1;for (int i = 2; i <= n; i++) {invs[i] = mul(MOD - MOD / i, invs[(int) (MOD % i)]);}return invs;}public final long[] arrayInv(long[] a) {int n = a.length;long[] l = new long[n + 1];long[] r = new long[n + 1];l[0] = r[n] = 1;for (int i = 0; i < n; i++) l[i + 1] = mul(l[i], a[i ]);for (int i = n; i > 0; i--) r[i - 1] = mul(r[i], a[i - 1]);long invAll = inv(l[n]);long[] invs = new long[n];for (int i = 0; i < n; i++) {invs[i] = mul(l[i], r[i + 1], invAll);}return invs;}public final long[] factorial(int n) {long[] ret = new long[n + 1];ret[0] = 1;for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], i);return ret;}public final long[] factorialInv(int n) {long facN = 1;for (int i = 2; i <= n; i++) facN = mul(facN, i);long[] invs = new long[n + 1];invs[n] = inv(facN);for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], i);return invs;}public final long[] rangePower(long a, int n) {a = mod(a);long[] pows = new long[n + 1];pows[0] = 1;for (int i = 1; i <= n; i++) pows[i] = mul(pows[i - 1], a);return pows;}public final long[] rangePowerInv(long a, int n) {a = mod(a);long[] invs = new long[n + 1];invs[n] = inv(pow(a, n));for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], a);return invs;}/** combinatric operations */public final long[][] combTable(int n) {long[][] comb = new long[n + 1][];for (int i = 0; i <= n; i++) {comb[i] = new long[i + 1];comb[i][0] = comb[i][i] = 1;for (int j = 1; j < i; j++) {comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]);}}return comb;}public final long naiveComb(long n, int r) {if (r < 0 || r > n) return 0;long num = 1, den = 1;for (int i = 0; i < r; i++) {num = mul(num, mod(n - i));den = mul(den, i + 1);}return div(num, den);}public final long naivePerm(long n, long r) {if (r < 0 || r > n) return 0;long res = 1;for (long i = 0; i < r; i++) res = mul(res, n - i);return res;}public final long naiveFactorial(int n) {return naivePerm(n, n);}}