fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. // #define int long long
  3. using namespace std;
  4.  
  5. #define _upgrade                  \
  6.     ios_base::sync_with_stdio(0); \
  7.     cin.tie(0);                   \
  8.     cout.tie(0);
  9. #define FOR(i, a, b) for (int i = a; i <= b; i++)
  10. #define FORB(i, a, b) for (int i = a; i >= b; i--)
  11. #define REP(i, a) for (int i = 0; i < a; i++)
  12. #define REP1(i, a) for (int i = 1; i < a; i++)
  13. #define REPB(i, a) for (int i = a - 1; i >= 0; i--)
  14. #define TRAV(a,x) for (auto& a: x)
  15. #define LINE "---------------------\n"
  16. #define ALL(A) A.begin(), A.end()
  17. #define LLA(A) A.rbegin(), A.rend()
  18. #define Q queue
  19. #define ff first
  20. #define ss second
  21. #define rs resize
  22. #define ins insert 
  23. #define fr front() 
  24. #define ts to_string
  25. #define pb push_back
  26. #define mp make_pair
  27. #define lb lower_bound 
  28. #define ub upper_bound 
  29. #define umap unordered_map
  30. #define sz(x) (int)x.size()
  31.  
  32. using ll = long long;
  33. using db = double;
  34. using uint = unsigned;
  35. using ull = unsigned long long;
  36. using umapII = unordered_map<int, int>;
  37. // PQ going up <int, VI, greater<int> >
  38. using VI = vector<int>;
  39. using VC = vector<char>;
  40. using VS = vector<string>;
  41. using VB = vector<bool>;
  42. using VVB = vector<VB>;
  43. using VVVB = vector<VVB>;
  44. using VVVVB = vector<VVVB>;
  45. using VVVVVB = vector<VVVVB>;
  46. using VLL = vector<ll>;
  47. using VVLL = vector<VLL>;
  48. using VVVLL = vector<VVLL>;
  49. using VVVVLL = vector<VVVLL>;
  50. using VD = vector<db>;
  51. using SI = set<int>;
  52. using SS = set<string>;
  53. using PII = pair<int, int>;
  54. using PDD = pair<db, db>;
  55. using PLL = pair<ll, ll>;
  56. using VPI = vector<PII>;
  57. using VVPI = vector<VPI>;
  58. using VVI = vector<VI>;
  59. using VVVI = vector<VVI>;
  60. using VVVVI = vector<VVVI>;
  61. using VVVVVI = vector<VVVVI>;
  62. // mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count() + reinterpret_cast<unsigned long>(new int) + *(new unsigned long));
  63. void eraseDups(VI& a) {
  64.     a.erase(unique(a.begin(), a.end()), a.end());
  65. }
  66. int strToInt(string&a) {
  67.     stringstream x(a);
  68.     int b;
  69.     x >> b;
  70.     return b;
  71. }
  72. int bitCnt(int a) {
  73.     bitset <64> b(a);
  74.     return b.count();
  75. }
  76. int bitCnt(string a) {
  77.     bitset <64> b(a);
  78.     return b.count();
  79. }
  80. VI readVI(int n) {
  81.     VI a(n);
  82.     REP(i, n) cin >> a[i];
  83.     return a;
  84. }
  85. VVI readVVI(int n, int m) {
  86.     VVI a(n, VI(m));
  87.     REP(i, n) a[i] = readVI(m);
  88.     return a;
  89. }
  90. VLL readVLL(ll n) {
  91.     VLL a(n);
  92.     REP(i, n) cin >> a[i];
  93.     return a;
  94. }
  95. VVLL readVVLL(ll n, ll m) {
  96.     VVLL a(n, VLL(m));
  97.     REP(i, n) a[i] = readVLL(m);
  98.     return a;
  99. }
  100.  
  101.  
  102. int gcd(int a, int b) {
  103.    if (b == 0) return a;
  104.    return gcd(b, a % b);
  105. }
  106.  
  107. void print(VI& a) {
  108.     for (auto el : a) {
  109.         cout << el << ' ';
  110.     }
  111.     cout << '\n';
  112. }
  113. void print(VPI& a) {
  114.     for (auto el : a) {
  115.         cout << el.ff << ',' << el.ss << ' ';
  116.     }
  117.     cout << '\n';
  118. }
  119.  
  120. void print(VI& a, int n) {
  121.     int cnt = 0;
  122.     for (auto el : a) {
  123.         if (cnt++ == n) break;
  124.         cout << el << ' ';
  125.     }
  126.     cout << '\n';
  127. }
  128. void print(VVI& a) {
  129.     for (auto el : a) {
  130.         print(el);
  131.     }
  132. }
  133. const int MOD1 = 1e9 + 7;
  134. const int MOD = 998244353;//7*19*2^23 +1;
  135. const int INF = 1.07e9;
  136. const ll INFF = INT64_MAX;
  137. const db EPS = 1e-9;
  138. const db PI = acos(-1.0); //M_PI;
  139. const int dx[] = {-1, 0, 1, 0};
  140. const int dy[] = {0, 1, 0, -1};
  141. /*
  142. |      ⣠⣶⡾⠏⠉⠙⠳⢦⡀⠀  ⠀⢠⠞⠉⠙⠲⡀
  143. |    ⣴⠿⠏⠀⠀⠀⠀⠀⠀⢳⡀⠀  ⡏⠀⠀ ⠀⠀ ⢷
  144. |⠀⠀⢠⣟⣋⡀⢀⣀⣀⡀⠀⣀⡀⣧⠀  ⢸⠀⠀⠀⠀   ⡇ ⠀
  145. | ⠀⢸⣯⡭⠁⠸⣛⣟⠆⡴⣻⡲⣿   ⣸⠀⠀OK.  ⡇
  146. |⠀⠀⣟⣿⡭⠀⠀⠀⠀⠀⢱⠀⠀⣿   ⢹⠀⠀⠀⠀⠀ ⡇
  147. |⠀⠀⠙⢿⣯⠄⠀⠀⠀⢀⡀⠀⠀⡿⠀  ⡇⠀⠀ ⠀ ⡼
  148. |⠀⠀⠀⠀⠹⣶⠆⠀⠀⠀⠀⠀⡴⠃ ⠀ ⠘⠤⣄⣠⠞⠀ ⠀
  149. |⠀⠀⠀⠀⢸⣷⡦⢤⡤⢤⣞⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀
  150. |⠀⢀⣤⣴⣿⣏⠁⠀⠀⠸⣏⢯⣷⣖⣦⡀⠀⠀⠀⠀⠀⠀
  151. |⢀⣾⣽⣿⣿⣿⣿⠛⢲⣶⣾⢉⡷⣿⣿⠵⣿⠀⠀⠀⠀⠀
  152. |⣼⣿⠍⠉⣿⡭⠉⠙⢺⣇⣼⡏⠀ ⠀⣄⢸⣿
  153. |⣿⣿⣧⣀⣿.........⣀⣰⣏⣘⣆⣀
  154.       
  155. |                                                    _         _   _
  156. |                                                   (_)       | | | |
  157.  _ __  _ __ ___   __ _ _ __ __ _ _ __ ___  _ __ ___  _ ___ ___| |_| |_
  158. | '_ \| '__/ _ \ / _` | '__/ _` | '_ ` _ \| '_ ` _ \| / __/ __| __| __|
  159. | |_) | | | (_) | (_| | | | (_| | | | | | | | | | | | \__ \__ \ |_| |_
  160. | .__/|_|  \___/ \__, |_|  \__,_|_| |_| |_|_| |_| |_|_|___/___/\__|\__|
  161. | |               __/ |
  162. |_|              |___/
  163.  _   _      _ _    __        __         _     _ 
  164. | | | | ___| | | __\ \      / /__  _ __| | __| |
  165. | |_| |/ _ \ | |/ _ \ \ /\ / / _ \| '__| |/ _` |
  166. |  _  |  __/ | | (_) \ V  V / (_) | |  | | (_| |
  167. |_| |_|\___|_|_|\___/ \_/\_/ \___/|_|  |_|\__,_|                                  
  168.  ____     __    _______    _______   __________
  169. |     \  |  |  |  _____|  /  _____) |____  ____|
  170. |  |\  \ |  |  | |__     (  (_____      |  |
  171. |  | \  \|  |  |  __|     \_____  \     |  | 
  172. |  |  \     |  | |_____    _____)  )    |  | 
  173. |__|   \____|  |_______|  (_______/     |__| 
  174.  
  175.  
  176.  
  177.  
  178.  
  179. */
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186. const int N = 5000;
  187.  
  188. ll fact[N+5], invFact[N+5];
  189. ll power(ll a, int b) {
  190.     ll ans = 1; 
  191.     while (b > 0) {
  192.         if (b & 1) ans = (ans * a) % MOD;
  193.         b >>= 1; 
  194.         a = (a * a) % MOD;
  195.     }
  196.     return ans;
  197. }
  198. ll inv(ll a, ll p) {
  199.     return power(a, p-2);
  200. }
  201. ll nCr(ll a, ll b) {
  202.     if (a < b || b < 0) return 0;
  203.     if (b == 0 || a == b) return 1;
  204.     return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
  205. }
  206. void init() {
  207.     fact[0] = fact[1] = 1;
  208.     for (int i = 2; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
  209.     invFact[N] = inv(fact[N], MOD);
  210.     for (int i = N-1; i >= 0; i--) invFact[i] = invFact[i+1] * ll(i+1) % MOD;
  211. }
  212.  
  213.  
  214.  
  215.  
  216. ll n, k;
  217. string s;
  218. void go () {
  219.     cin >> n >> k >> s;
  220.     ll ans = 0;
  221.     VI pos;
  222.     for (int i = 0; i < n; i++) 
  223.         if (s[i] == '1') pos.pb(i);
  224.  
  225.     if (k > pos.size() || k == 0) {
  226.         cout << "1\n";
  227.         return;
  228.     }
  229.     ll curLen = (pos.size() == k ? n : pos[k]), zero = 0;
  230.     ans = (ans + nCr(curLen, k))%MOD;
  231.     for (int i = pos[k], j = -1; i < n; i++) {
  232.         if (s[i] == '1') {
  233.             curLen = i - pos[++j];
  234.             zero = curLen - k;
  235.             if (zero > 0)
  236.                 ans = (ans + nCr(curLen-1, zero-1))%MOD;
  237.         } else {
  238.             curLen = i - pos[j];
  239.             zero = curLen - k;
  240.             ans = (ans + nCr(curLen-1, k-1))%MOD;
  241.         }
  242.     }
  243.     cout << ans << '\n';
  244. }
  245.  
  246.  
  247.  
  248. signed main () {
  249.  
  250. #ifndef ONLINE_JUDGE
  251.     freopen("in.txt", "r", stdin);
  252.     freopen("out.txt", "w", stdout);
  253. #endif
  254.     _upgrade
  255.     int T = 1;
  256.     // cin >> T;
  257.     init();
  258.     while(T--) go();
  259.     return (0-0); //<3
  260. }
  261.  
  262. /* stuff you should look for
  263.     * int overflow, array bounds
  264.     * special cases (n=1?)
  265.     
  266. */
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:280:1: error: stray ‘\302’ in program
  
 ^
prog.cpp:280:2: error: stray ‘\240’ in program
  
  ^
stdout
copy 
Standard output is empty
https://ideone.com/neTGqI
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!