KTLT15. Chuỗi nhị phân

Tiêu đề: KTLT15. Chuỗi nhị phân Thu May 12, 2022 7:55 pm

KTLT15. Chuỗi nhị phân
Xét xâu nhị phân, tức là xâu chỉ chứa các ký tự trong tập {0, 1}. Gọi k là số lượng xâu nhị phân độ dài n (1 ≤ n ≤ 10^4) chứa xâu S (độ dài không quá 100) như một xâu con (các ký tự liên tiếp) đúng một lần.
Yêu cầu: Hãy tính phần dư của kết quả chia k cho 10^9+7.
Dữ liệu: Vào từ file văn bản BINARY.INP:
• Dòng thứ nhất chứa số nguyên n,
• Dòng thứ hai chứa xâu S.
Kết quả: Đưa ra file văn bản BINARY.OUT một số nguyên – kết quả tìm được.
Ví dụ:
BINARY.INP
4
01
BINARY.OUT
10

Tổng số bài gửi : 16 Join date : 10/05/2022

Code:: #include <iostream>
#include <math.h>

using namespace std;

int N,dem;
string s;

string decToBin(int n){
string ans = "";
while (n > 0) {
ans = char (n % 2 + '0') + ans;
n /= 2;
}
while (ans.length() < N)
ans = "0" + ans;
return ans;
}

int main(){
cin >> N >> s;
int N_2 = pow(2, N);
for (int i = 0; i < N_2; i++)
{
if(decToBin(i).find(s) <= decToBin(i).size())
dem++;
}
cout<< dem % (int)(1e9 + 7);
}

Tổng số bài gửi : 27 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>

using namespace std;

int res,a[10004],n;
string s;

void xet(){
string st="";
int dem=0;
for (int i=1;i<=n;++i)
st=st+char(a[i]+48);
while (st.find(s)!=-1){
dem++;
st.replace(st.find(s),s.size(),"2");
if (dem>1) break;
}
if (dem==1) {res++; }
}

void sinh(int i){
for (int j=0;j<=1;++j){
a[i]=j;
if (i==n) xet();
else sinh(i+1);
}
}

int main()
{
freopen("BINARY.inp","r",stdin);
freopen("BINARY.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
cin>>s;
sinh(1);
cout<<res;
}

» Bùi Kim Chi
» Bài 58. Đếm phần tử
» Bài 59. Tìm phần tử nhỏ nhất
» Bài 94. Đếm phân phối
» Nguyễn Phan Như Quỳnh