Sequences with Bounded Frequency
National Olympiad — Regional round
Submission name: sequences.cpp
Problem summary
Count length-N ordered sequences whose elements are from 1 through M, with no value appearing more than K times.
Input
N M K.
Output
The count modulo 998244353.
Constraints
1 ≤ N,M,K ≤ 300.
Worked example
An independently prepared example for this explanation.
Input
3 3 1
Output
6
Solution analysis
- Process possible values one at a time. Let dp[s] count arrangements of s positions using processed values.
- When introducing the next value exactly c times, insert its c indistinguishable copies in choose(s+c,c) ways.
- Sum transitions for 0≤c≤K and s+c≤N; precompute binomial coefficients modulo the modulus.
Why it works
Removing all copies of the newest value uniquely recovers an earlier arrangement and their chosen positions, proving the transition counts each sequence once.
Complexity: O(M·N·min(K,N)+N²) time; O(N²) space.
Watch out. Sequences are ordered; merely counting frequency vectors is insufficient.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Removing all copies of the newest value uniquely recovers an earlier arrangement and their
// chosen positions, proving the transition counts each sequence once.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
const long long P=998244353;
vector<vector<long long>>c(n+1,vector<long long>(n+1));
for(int i=0;i<=n;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
}
}
vector<long long>d(n+1),e(n+1);
d[0]=1;
while(m--){
fill(e.begin(),e.end(),0);
for(int s=0;s<=n;s++){
for(int t=0;t<=k&&s+t<=n;t++){
e[s+t]=(e[s+t]+d[s]*c[s+t][t])%P;
}
}
d.swap(e);
}
cout<<d[n]<<'\n';
}