NYOJ B : CTX学长的01串

xiaoxiao2021-02-28  1

B : CTX学长的01串

题目描述

想AK,必须过了我这一关(偷笑)。 给你一个01字符串只包括字符0和1(例如:0101010101010011010) 现在CTX学长想要考考你们,这个01串中有多少的子序列。 子序列的定义是这样的,可以在01串中找一些字符(不能改变字符的顺序)组成一个新的串, 例如01,你可以找到的子序列是"0","1","01". 例如0110,你可以找到的子序列是"0","1","01","11","10","00","011","110","010","0110".

输入

输入一个T,有T组数据。(0<T<=100) 接来下有T行,每行输入一个01串,0<长度<=100000。

输出

输出01串中有多少个不同的子序列。答案太大,输出对1000000007取余之后的结果

样例输入

复制 4 10 101 1100 00000

样例输出

复制 3 6 8 5

提示

第一个样例所包含的子序列为“0”,“1”,“10”。一共有3个子序列 第二个样例所包含的子序列为“0”,“1”,“01”,“10”,“11”,“101”。一共有6个子序列 第三个样例所包含的子序列为“0”,“1”,“00”,“10”,“11”,“100”,“110”,“1100”。一共有8个子序列 第四个样例所包含的子序列为“0”,“00”,“000”,“0000”,“00000”。一共有5个子序列. 这道题我还没做出来,就先放题解,我的代码等做出来了再放。 题解: #include<bits/stdc++.h> using namespace std; const long long mod=1000000007; char s[110000]; int main() { int t; scanf("%d",&t); while(t--) { scanf("%s",s); int k=strlen(s); long long a=0,b=0,c=0,d=1; long long sum=0; for(int i=0;i<k;i++) { if(s[i]=='0') { a+=b; c+=d; d+=b; b=0; } else if(s[i]=='1') { a+=c; b+=d; d+=c; c=0; } a%=mod; b%=mod; c%=mod; d%=mod; } sum=(a+b+c+d-1)%mod; printf("%lld\n",sum); } }
转载请注明原文地址: https://www.6miu.com/read-1750369.html

最新回复(0)