Submission #43658495

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import std;
void main () {
    int N = readln.chomp.to!int;
    string S = readln.chomp;
    solve(N, S);
}
void solve (int N, string S) {
    // dp[i][j] := i文字目に来た時点で、それまでの否定論理和がjである場合の数
    long[][] dp = new long[][](N, 2);
    // initialize
    dp[0][] = 0;
    if (S[0] == '0') {
        dp[0][0] = 1;
    } else {
        dp[0][1] = 1;
    }
    foreach (i; 1..N) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import std;

void main () {
    int N = readln.chomp.to!int;
    string S = readln.chomp;
    solve(N, S);
}

void solve (int N, string S) {
    // dp[i][j] := i文字目に来た時点で、それまでの否定論理和がjである場合の数
    long[][] dp = new long[][](N, 2);

    // initialize
    dp[0][] = 0;
    if (S[0] == '0') {
        dp[0][0] = 1;
    } else {
        dp[0][1] = 1;
    }

    foreach (i; 1..N) {
        if (S[i] == '0') {
            dp[i][0] = 0;
            dp[i][1] = dp[i-1][0] + dp[i-1][1];
        } else {
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }
        dp[i][S[i]-'0']++;
    }

    long ans = 0;
    foreach (i; 0..N) {
        ans += dp[i][1];
    }

    writeln(ans);
}

Submission Info

Judge Result