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.

include

include

include

include

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.