# CAN Anyone Answer me

count how many sequences of length n exist consisting only of
numbers [0 , k] such that each number occurs at least t. ?
What is the Solution of that ?
With Explain Plsssssss!!

could you provide an example
like sample input and output

n = 3 , k = 1 , t = 1 ;

[0 , 1 , 0] is valid
[1 , 0 , 1]is valid
why ?
because 0 and 1 appears at least t in the sequnce ;

@mahjop95
I have used map ,vector and some algorithms.
This program provides you with the number elements has repeated at least ‘t’ times.
eg:
n = 3 , k = 1 , t = 1 ;
[1,0,1]
out put: 2
since 0 and 1 have satisfied the requirement.

using namespace std;

int main() {
int n,k,t;
cin>>n>>k>>t;
vector vec(n);
map<int,int>m;
for(int i=0;i<n;i++)
{
cin>>vec[i];
}
sort(vec.begin(),vec.end());
for(int i=0;i<=n;i++)
{
m[vec[i]]=count(vec.begin(),vec.end(),vec[i]);
}

int c=0;
for(auto it:m)
{
if(it.second>=t)
c++;
}
cout<<c<<endl;

return 0;

}

Let me know if this is what you wanted, and whether you can understand.

NOOOOOOOOOOOO
It’s Hard than this
if I Told you n = 1e5 , k = 1e5 , t = 434

I think the answer can be very large. You need the answer modulo 998244353 or 1000000007?
The answer is the coefficient of x^n in n!(\sum_{i=t}^{n}(x^i/i!))^{k+1} .
This can be calculated in O(n\log n \log k) by using NTT and repeated squaring, and it works quickly enough even with the constraint of n,k \leq 10^5.