Fun Count Not Fun#12383

Fun Count Not Fun (Editorial)

When we remove a contiguous subarray of length $k$ , the array shrinks, but the relative positions of the remaining elements follow a strict mathematical rule.

1. The Index Invariance

When a subarray of length $k$ is removed starting at some index $i$ , any element originally at index $j$ (where $j > i + k$ j > i+k) shifts left by exactly $k$ units.

Because the shift is exactly $k$ , the property $j (mod k)$ j \pmod k remains unchanged.
This means the element that ends up at the $1^{s t}$ 1^{st} position of the final array must have originally been at an index $i_{1} \equiv 1 (mod k)$ i_1 \equiv 1 \pmod k.
Generally, the element at the $j^{t h}$ j^{th} position of the final array must have originally been at an index $i_{j} \equiv j (mod k)$ i_j \equiv j \pmod k.

2. Defining the Constraints

Let $n$ be the initial length and $k$ be the removal block size.

The final length will be $r = n (mod k)$ r = n \pmod k.
Let $q = ⌊ n / k ⌋$ q = \lfloor n/k \rfloor be the total number of blocks we can remove.
We need to choose $r$ indices $(i_{1}, i_{2}, \dots, i_{r})$ (i_1, i_2, \dots, i_r) from the original $1 \dots n$ such that:
1. $1 \leq i_{1} < i_{2} < \dots < i_{r} \leq n$ 1 \le i_1 < i_2 < \dots < i_r \le n (Relative order is preserved).
2. $i_{j} \equiv j (mod k)$ i_j \equiv j \pmod k for all $j$ .

3. Transformation to Stars and Bars

To satisfy the modulo condition, we can rewrite each original index as:

i_{j} = j + a_{j} \cdot k

i_j = j + a_j \cdot k

Where $a_{j}$ a_j is the number of $k$ -sized blocks skipped or deleted to the left of the $j^{t h}$ j^{th} element.

Substituting this into our ordering constraint ( $i_{j} < i_{j + 1}$ i_j < i_{j+1}):

j + a_{j} \cdot k < (j + 1) + a_{j + 1} \cdot k ⟹ a_{j} \leq a_{j + 1}

j + a_j \cdot k < (j+1) + a_{j+1} \cdot k \implies a_j \le a_{j+1}

And for the boundary ( $i_{r} \leq n$ i_r \le n):

r + a_{r} \cdot k \leq r + q \cdot k ⟹ a_{r} \leq q

r + a_r \cdot k \le r + q \cdot k \implies a_r \le q

This reduces the problem to choosing a non-decreasing sequence of $r$ integers where each $a_{j} \in [0, q]$ a_j \in [0, q].

4. The Final Formula

This is a classic "Stars and Bars" problem (choosing $r$ items from $q + 1$ q+1 possible values with replacement). The number of ways is:

(r ( q + 1 ) + r - 1) = (r q + r)

\binom{(q+1) + r - 1}{r} = \binom{q+r}{r}

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

const ll mod = 998244353 ;
const ll N = 1e6 + 5; 
vector <ll> factorial(N); 
vector <ll> invfact(N); 
 
ll binpow(ll a , ll b) { 
 ll ans = 1; 
 ll index = a; 
 while (b) { 
  if (b & 1) { 
   ans = (ans * index) % mod; 
  } 
  index = (index * 1LL * index) % mod; 
  b >>= 1; 
 } 
 return ans % mod; 
} 
 
void fillfact() { 
 factorial[0] = 1; 
 for (int i = 1; i < N; i++) { 
  factorial[i] = (factorial[i - 1] * i) % mod; 
 } 
} 
 
void fillinvfact() { 
 invfact[N - 1] = (binpow(factorial[N - 1] , mod - 2)) % mod; 
 for (int i = N - 2; i >= 0; i--) { 
  invfact[i] = ((i + 1) * 1LL * invfact[i + 1]) % mod; 
 } 
} 
 
ll ncr(int n , int r) { 
 if (n < r) return 0; 
 if (n < 0 || r < 0) return 0; 
 ll ans = (factorial[n] * 1LL * invfact[n - r]) % mod; 
 ans = (ans * invfact[r]) % mod; 
 return ans % mod; 
} 

void solve() {
  
  int n , k ;
  cin >> n >> k ;
  int sum = (n % k) ;
  int f = ((n + k - 1) / k) ;
  cout << ncr(sum + f - 1 , sum) << endl ;
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("output.txt", "w", stdout);
    // freopen("input.txt", "r", stdin);
    int t;
    cin >> t ;
    fillfact() ;
    fillinvfact() ;
    while (t--) {
        solve();
    }
    return 0;
}

C++