20111 无解的子序列计数

题目描述

递归算法是一种非常优美的算法，一个好的递归可以过百万 ——题记

小问小一个问题，问题很简单，小将给出一个长度为的串，小需要回答这个串里面有多少个子序列为 01 。

小觉得这道题太简单了，就把问题扔给了你，相信聪明的你一定能解决。

注：子序列不需要连续。

输入格式

共两行。

第一行一个整数，表示串的长度。

第二行为一个只包含的长度为的串。

输出格式

共一行，表示小需要回答的答案。

样例

Input #1

5
10110

Output #1

数据范围与提示

对于的数据，。

分类标签

[字符串] [枚举]

C++题解代码

#include <bits/stdc++.h>
using namespace std;

int a;
long long d;
long long c;
char b;


int main() {
  cin>>a;
  c = 0;
  d = 0;
  for (int i = 0; i < a; i++) {
    cin>>b;
    if (b == '0') {
      c++;
    } else {
      d += c;
    }
  }
  cout<<d;
  return 0;
}

Blockly题解代码图片