Submission #5848468


Source Code Expand

Copy
#define DEBUG 0

/**
 * File    : E.cpp
 * Author  : Kazune Takahashi
 * Created : 6/9/2019, 9:16:59 PM
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

/*
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}

void No()
{
  cout << "No" << endl;
  exit(0);
}
*/

/*
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
*/

const ll MOD = 1000000007;

string L;
ll dp[100010][2];

int main()
{
  cin >> L;
  int N = L.size();
  dp[0][0] = 1;
  for (auto i = 0; i < N; i++)
  {
    dp[i + 1][1] += (3 * dp[i][1]) % MOD;
    dp[i + 1][1] %= MOD;
    if (L[i] == '0')
    {
      dp[i + 1][0] += dp[i][0];
      dp[i + 1][0] %= MOD;
    }
    else
    {
      dp[i + 1][1] += dp[i][0];
      dp[i + 1][1] %= MOD;
      dp[i + 1][0] += (2 * dp[i][0]) % MOD;
      dp[i + 1][0] %= MOD;
    }
#if DEBUG == 1
    cerr << "dp[" << i + 1 << "][" << 0 << "] = " << dp[i + 1][0] << endl;
    cerr << "dp[" << i + 1 << "][" << 1 << "] = " << dp[i + 1][1] << endl;
#endif
  }
  cout << (dp[N][0] + dp[N][1]) % MOD << endl;
}

Submission Info

Submission Time
Task E - Sum Equals Xor
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1483 Byte
Status
Exec Time 7 ms
Memory 2048 KB

Test Cases

Set Name Score / Max Score Test Cases
All 500 / 500 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 0 / 0 sample_01, sample_02
Case Name Status Exec Time Memory
all_one 7 ms 2048 KB
one_one 6 ms 2048 KB
only_one 1 ms 256 KB
random_large_01 6 ms 2048 KB
random_large_010 6 ms 2048 KB
random_large_02 6 ms 2048 KB
random_large_03 6 ms 2048 KB
random_large_04 6 ms 2048 KB
random_large_05 6 ms 2048 KB
random_large_06 6 ms 2048 KB
random_large_07 6 ms 2048 KB
random_large_08 6 ms 2048 KB
random_large_09 6 ms 2048 KB
random_small_01 1 ms 256 KB
random_small_02 1 ms 256 KB
random_small_03 1 ms 256 KB
random_small_04 1 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB