写了两种做法,
一种是提前算出每次操作会增加多少个一,直接加在ans 上面,然后根据每次删除的数,更改每次增加的一的数量。只能对12个点
int n;
string a;
int ans;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a;
up(i,0,a.size()-2){
if(a[i]!='1'&&a[i+1]!='1'){
cout<<-1;
exit(0);
}
}
int sum=0;
up(i,0,a.size()-2){
if(a[i]=='1'&&a[i+1]!='1')sum=(sum+a[i+1]-'1')%mod;
}
ans=a.size()-1;
dn(i,a.size()-1,1){
ans=(ans+sum)%mod;
sum=(sum-(a[i]-'1'));
}
cout<<ans;
return 0;
}
然后又写了一个递推的做法,感觉本质上是一样的,却能对。
int n;
string a;
int ans;
int f[N];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a;
up(i,0,a.size()-2){
if(a[i]!='1'&&a[i+1]!='1'){
cout<<-1;
exit(0);
}
}
f[n-1]=1;
dn(i,n-2,0){
f[i]=(f[i+1]*(a[i+1]-'0')+1)%mod;
}
if(a[0]=='1')cout<<f[0]-1<<endl;
else cout<<f[1];
return 0;
}