fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5.     static final int MOD = 998244353;
  6.     static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  7.     static StringTokenizer tokenizer;
  8.  
  9.     public static void main(String[] args) throws Exception {
  10.         char[] s = br.readLine().trim().toCharArray();
  11.         int m = Integer.parseInt(br.readLine().trim());
  12.         int len = s.length;
  13.         int[] must = new int[len];
  14.         Arrays.fill(must, -1);
  15.         for (int i = 0; i < m; i++) {
  16.             String[] parts = br.readLine().split(" ");
  17.             int p = Integer.parseInt(parts[0]);
  18.             int o = Integer.parseInt(parts[1]);
  19.             if (p < len) {
  20.                 must[len - 1 - p] = o;
  21.             }
  22.         }
  23.  
  24.         long[][][] dp = new long[len + 1][2][2];
  25.         dp[0][1][0] = 1;
  26.         for (int i = 0; i < len; i++) {
  27.             for (int tight = 0; tight < 2; tight++) {
  28.                 for (int has = 0; has < 2; has++) {
  29.                     if (dp[i][tight][has] == 0) continue;
  30.                     int maxDigit = (tight == 1) ? (s[i] - '0') : 1;
  31.                     for (int d = 0; d <= maxDigit; d++) {
  32.                         if (must[i] != -1 && d != must[i]) continue;
  33.                         int newTight = (tight == 1 && d == maxDigit) ? 1 : 0;
  34.                         int newHas = (has == 1 || d == 1) ? 1 : 0;
  35.                         dp[i + 1][newTight][newHas] = (dp[i + 1][newTight][newHas] + dp[i][tight][has]) % MOD;
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         long ans = 0;
  41.         for (int tight = 0; tight < 2; tight++) {
  42.             for (int has = 0; has < 2; has++) {
  43.                 ans = (ans + dp[len][tight][has]) % MOD;
  44.             }
  45.         }
  46.         System.out.println(ans);
  47.     }
  48. }
Success #stdin #stdout 0.07s 55012KB
comments (?)
stdin
copy 
1011
2
1 1
3 0
stdout
copy 
4
https://ideone.com/HIhP6v
language:
Java (HotSpot 12)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!