結果
| 問題 | No.1710 Minimum OR is X |
| ユーザー |
 cyclerecycle9
|
| 提出日時 | 2021-12-06 03:48:02 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 209 ms / 2,000 ms |
| コード長 | 5,325 bytes |
| コンパイル時間 | 2,511 ms |
| コンパイル使用メモリ | 81,228 KB |
| 実行使用メモリ | 62,848 KB |
| 最終ジャッジ日時 | 2024-07-07 08:50:27 |
| 合計ジャッジ時間 | 7,976 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.math.BigDecimal;import java.math.RoundingMode;import java.util.*;import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;import java.io.File;import java.io.FileDescriptor;import java.io.FileOutputStream;import java.io.OutputStream;import java.io.UncheckedIOException;import java.lang.Thread.State;import java.lang.reflect.Field;import java.nio.CharBuffer;import java.nio.charset.CharacterCodingException;import java.nio.charset.CharsetEncoder;import java.nio.charset.StandardCharsets;public class Main {static final long MOD1=1000000007;static final long MOD=998244353;static long ans=0;public static void main(String[] args){PrintWriter out = new PrintWriter(System.out);InputReader sc=new InputReader(System.in);int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();char[] cs = sc.next().toCharArray();long[][] dp = new long[m+1][n+1];dp[0][n] = 1l;Binomial bi = new Binomial();long[] two = any_mod_pow(2l, 1000, MOD);for (int i = 0; i < m; i++) {for (int j = 0; j <= n; j++){if (cs[i]=='0'){for (int j2 = k; j2 <= j; j2++){dp[i+1][j2] = (dp[i+1][j2] + (((dp[i][j] * bi.nCk(j, j2))%MOD)*two[n-j])%MOD)%MOD;}}else {for (int j2 = 0; j2 < k; j2++) {long a = (dp[i][j] * bi.nCk(j, j2))%MOD;a = (a*two[n-j])%MOD;dp[i+1][j] = (dp[i+1][j] + a)%MOD;}}}}long ans = 0;for (int i = 0; i <= n; i++){//System.out.println(dp[m][i]);ans = (ans + dp[m][i])%MOD;}System.out.println(ans);}static long[] any_mod_pow(long a,int size,long MOD){long[] pow = new long[size+1];pow[0] = 1l;for (int i = 1; i < pow.length; i++) {pow[i] = (pow[i-1]*a)%MOD;}return pow;}//aのn乗の配列static class Binomial{int MAX = 510000;//ほしいサイズlong[] fac=new long[MAX];long[] finv=new long[MAX];long[] inv=new long[MAX];public Binomial(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[(int) (MOD%i)] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}//facがx!、finvがx!の逆元,10^7くらいまでのテーブル(MAXまで)}long nCk(int n,int k) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}long fac(int n) {return fac[n];}long fac_inv(int n) {return finv[n];}}static class InputReader {private InputStream in;private byte[] buffer = new byte[1024];private int curbuf;private int lenbuf;public InputReader(InputStream in) {this.in = in;this.curbuf = this.lenbuf = 0;}public boolean hasNextByte() {if (curbuf >= lenbuf) {curbuf = 0;try {lenbuf = in.read(buffer);} catch (IOException e) {throw new InputMismatchException();}if (lenbuf <= 0)return false;}return true;}private int readByte() {if (hasNextByte())return buffer[curbuf++];elsereturn -1;}private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}private void skip() {while (hasNextByte() && isSpaceChar(buffer[curbuf]))curbuf++;}public boolean hasNext() {skip();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (!isSpaceChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public int nextInt() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}int res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public long nextLong() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}long res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public double nextDouble() {return Double.parseDouble(next());}public int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = nextInt();return a;}public double[] nextDoubleArray(int n) {double[] a = new double[n];for (int i = 0; i < n; i++)a[i] = nextDouble();return a;}public long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++)a[i] = nextLong();return a;}public char[][] nextCharMap(int n, int m) {char[][] map = new char[n][m];for (int i = 0; i < n; i++)map[i] = next().toCharArray();return map;}}}