fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 998244353;
  5.  
  6. long long modpow(long long a, long long b) {
  7.     long long res = 1;
  8.     while (b) {
  9.         if (b & 1) res = res * a % MOD;
  10.         a = a * a % MOD;
  11.         b >>= 1;
  12.     }
  13.     return res;
  14. }
  15.  
  16. long long modinv(long long a) {
  17.     return modpow(a, MOD - 2);
  18. }
  19.  
  20. long long nCr(long long m, int r) {
  21.     if (m < r || r < 0) return 0;
  22.     long long num = 1;
  23.     for (int i = 0; i < r; i++) {
  24.         num = num * ((m - i) % MOD) % MOD;
  25.     }
  26.     long long den = 1;
  27.     for (int i = 1; i <= r; i++) {
  28.         den = den * i % MOD;
  29.     }
  30.     return num * modinv(den) % MOD;
  31. }
  32.  
  33. int main() {
  34.     long long n;
  35.     int k;
  36.     cin >> n >> k;
  37.  
  38.     long long N = n - (long long)k * (k - 1) / 2;
  39.     if (N < k) {
  40.         cout << 0 << endl;
  41.         return 0;
  42.     }
  43.  
  44.     long long ans = 0;
  45.     for (int j = 0; j <= k; j++) {
  46.         long long m = N - j * (k + 1) - 1;
  47.         long long term = nCr(m, k - 1);
  48.         if (j % 2 == 0) {
  49.             ans = (ans + nCr(k, j) * term) % MOD;
  50.         } else {
  51.             ans = (ans - nCr(k, j) * term % MOD + MOD) % MOD;
  52.         }
  53.     }
  54.     cout << ans << endl;
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
10 3
stdout 
12
https://ideone.com/NRxMMc
language:
C++14 (clang 8.0)
created:
4 hours ago
visibility:
public

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!