Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #5848468

Source Code Expand

Copy
```#define DEBUG 0

/**
* File    : E.cpp
* Author  : Kazune Takahashi
* Created : 6/9/2019, 9:16:59 PM
*/

#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 2019-06-09 21:44:57+0900 E - Sum Equals Xor kazunetakahashi C++14 (GCC 5.4.1) 500 1483 Byte AC 7 ms 2048 KB

#### Judge Result

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