【题解】和零在一起

题意

给你一个01字符串，要求将该字符串划分为几个部分，且每个部分有且仅有一个，问一共有多少种划分方案，答案可能很大对取模。

题解

我们以每个作为分界线，由于每个部分只能含有一个，所以和之间是独立的。那么我们只用考虑相邻两个之间的划分方案数，若两个之间隔了个，那么相当于有个空可以用来插入隔板，所以两个之间的划分方案数就是，那么整体的方案数实际上就是，相邻的之间的乘积。由于是乘积会比较大，所以答案需要取模。我们可以先记录下来每个的下标，那么两个的下标之差就是他们之间的个数+1了，然后遍历一遍记录的的下标即可。

复杂度

时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
vector<int>a;
int main()
{
    int n;
    scanf("%d",&n);
    string str;
    cin>>str;
    long long ans=1;
    for(int i=0;i<n;i++)
    {
        if(str[i]=='0')
            a.push_back(i);
    }
    if(a.size()==0)
        printf("0\n");
    else if(a.size()==1)
        printf("1\n");
    else
    {
        for(int i=1;i<a.size();i++)
            ans=ans*(a[i]-a[i-1])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}