1295-B, *1700

Problem - B - Codeforces

문제

• 문자열 $s$가 주어질 때 무한길이 문자열 $sss...$을 생각하자
• 무한길이 문자열에서 $\mathrm{bal(i)}=x$인 $\mathrm{prefix(i)}$의 개수는?
• $\mathrm{prefix(i)}$는 i번째 문자까지를 포함한 문자열의 prefix 로 정의한다
• $\mathrm{bal(i)}$는 $\mathrm{prefix(i)}$에서 (0 의 빈도수)-(1의 빈도수) 로 정의한다

 

$O(n)$

s의 주기성과 연관하여 bal(i)를 관찰하자

3 10
010

$$\mathrm{bal(i)}=\left \lfloor \frac{i}{n} \right \rfloor \mathrm{bal(n-1)}+\text{bal}(i\text{ mod(n)}),\ \mathrm{bal(-1)}=0$$

let key = bal(n-1)
i) key = 0 일때
가. 주황색 부분에 x와 같은 bal(i)가 존재 ~ -1
나. 주황색 부분에 x와 같은 bal(i)가 존재 ~ 0 이거나 1 (x=0 이면 1이고 그 외의 경우는 0)

ii) key ≠ 0 일때
$\mathrm{bal(i)}=\left \lfloor \frac{i}{n} \right \rfloor \text{key}+\text{bal}(i\text{ mod(n)})=x$
인 i 의 개수를 구하면 된다
division algorithm 에 의해
i = kn+r, 0 ≤ r < n
인 정수 k, r이 유일하게 존재하고 이를 이용하여 위 식을 다시 쓰면 다음과 같다
$\mathrm{bal(i)}=k\cdot \text{key }+\text{bal}(r)=x$
r 을 0 부터 n-1 까지 고정하면 위 식은 k 에 관한 일차방정식이고, k 가 결정되면 i 가 결정되므로
위 방정식의 해의 개수가 구하려는 값이다

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;
        string s;
        cin >> s;
        vector<int> balance(n);
        int zero = 0, one = 0;
        ooop(i, n){
            if(s[i] == '0') zero++;
            else one++;
            balance[i] = zero-one;
        }
        int key = balance[n-1];
 
        if(key == 0){
            bool exist = false;
            for(const auto& e: balance){
                if(x == e) {
                    exist = true;
                    break;
                }
            }
 
            if(exist) cout << -1 << endl;
            else if(x == 0) cout << 1 << endl;
            else cout << 0 << endl;
        }
        else{
            if(key < 0){
                key *= -1;
                x *= -1;
                for(auto& e: balance) e *= -1;
            }
            int res = 0;
            if(x == 0) res++;
            ooop(i, n){
                if((x-balance[i])%key == 0){
                    int crit = (x-balance[i])/key;
                    if(crit >= 0) res++;
                }
            }
 
            cout << res << endl;
        }
 
    }
 
 
    return 0;
}cs