Submission #21630951

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

ll dp[100002][2];
const ll MOD = 1000000007;

int main()
{
  string s;
  cin >> s;

  dp[0][0] = 1;
  dp[0][1] = 0;

  int n = s.size();

  for (int i = 1; i <= n; i++){
    int d = s[i-1] - '0';
    if (d == 0){
      dp[i][0] = dp[i-1][0];
      dp[i][1] = dp[i-1][1] * 3 % MOD;
    } else { // d == 1
      dp[i][0] = dp[i-1][0] * 2 % MOD;
      dp[i][1] = (dp[i-1][0] + dp[i-1][1] * 3 % MOD) % MOD;
    }
  }

  ll ans = (dp[n][0] + dp[n][1]) % MOD;
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task E - Sum Equals Xor
User unnohideyuki
Language C++ (GCC 9.2.1)
Score 500
Code Size 703 Byte
Status AC
Exec Time 12 ms
Memory 5228 KiB

Judge Result

Set Name All Sample
Score / Max Score 500 / 500 0 / 0
Status
AC × 19
AC × 2
Set Name Test Cases
All all_one, one_one, only_one, random_large_01, random_large_010, random_large_02, random_large_03, random_large_04, random_large_05, random_large_06, random_large_07, random_large_08, random_large_09, random_small_01, random_small_02, random_small_03, random_small_04, sample_01, sample_02
Sample sample_01, sample_02
Case Name Status Exec Time Memory
all_one AC 11 ms 5228 KiB
one_one AC 8 ms 5148 KiB
only_one AC 2 ms 3480 KiB
random_large_01 AC 12 ms 5120 KiB
random_large_010 AC 11 ms 5172 KiB
random_large_02 AC 9 ms 5224 KiB
random_large_03 AC 12 ms 5136 KiB
random_large_04 AC 7 ms 5164 KiB
random_large_05 AC 8 ms 5220 KiB
random_large_06 AC 8 ms 5168 KiB
random_large_07 AC 6 ms 5224 KiB
random_large_08 AC 9 ms 5140 KiB
random_large_09 AC 10 ms 5228 KiB
random_small_01 AC 3 ms 3460 KiB
random_small_02 AC 2 ms 3540 KiB
random_small_03 AC 3 ms 3536 KiB
random_small_04 AC 3 ms 3536 KiB
sample_01 AC 2 ms 3612 KiB
sample_02 AC 2 ms 3536 KiB