Advertisement
Fshl0

Untitled

Jan 23rd, 2022
863
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. //#define mp make_pair
  5. #define pb push_back
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9.  
  10. const int MOD = 998244353;
  11. const int N = 5e3 + 9;
  12. const int M = 1e6 + 9;
  13. const int INF = 2e9 + 5;
  14. const int K = 100 + 9;
  15.  
  16. ll nCr[N][N], res, ones[N];
  17.  
  18. ll Flex (ll x) {
  19.     return ((x % MOD) + MOD) % MOD;
  20. }
  21.  
  22. ll calc (int l, int r) {
  23.     return nCr[r - l + 1][ones[r] - ones[l - 1]];
  24. }
  25.  
  26. int main () {
  27.     int n, k;
  28.     cin >> n >> k;
  29.    
  30.     string s;
  31.     cin >> s;
  32.     s = "3" + s;
  33.    
  34.     nCr[1][0] = nCr[1][1] = 1;
  35.     for (int i = 2; i < N; i++) {
  36.         nCr[i][0] = 1;
  37.         for (int j = 1; j <= i; j++)
  38.             nCr[i][j] = Flex (nCr[i - 1][j] + nCr[i - 1][j - 1]);
  39.     }
  40.    
  41.     if (k == 0) {
  42.         puts ("1");
  43.        
  44.         return 0;
  45.     }
  46.    
  47.     for (int i = 1; i <= n; i++)
  48.         ones[i] = ones[i - 1] + (s[i] == '1');
  49.    
  50.     if (ones[n] < k) {
  51.         puts ("1");
  52.        
  53.         return 0;
  54.     }  
  55.                
  56.     int last = -1;
  57.     for (int i = 1; i <= n; i++) {
  58.         int newLast = i, cnt = 0;
  59.         for (; newLast <= n; newLast++) {
  60.             cnt += (s[newLast] == '1');
  61.            
  62.             if (cnt == k && newLast == n)
  63.                 break;
  64.            
  65.             if (cnt == k && s[newLast + 1] == '1')
  66.                 break;
  67.         }
  68.        
  69.         if (newLast > n)
  70.             break;
  71.         res = Flex (res + calc (i, newLast));
  72.        
  73.         if (last == -1) {
  74.             newLast = last;
  75.            
  76.             continue;
  77.         }
  78.        
  79.         res = Flex (res - calc(i, last));
  80.         last = newLast;
  81.     }
  82.    
  83.     cout << res << "\n";
  84.    
  85.     return 0;
  86. }
  87.  
  88.  
  89.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement