RUET IUPC Problem J / NNT + Divide and Conquer

/***
 created: 2022-08-14-23.16.33
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define int long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'
#define PI acos(-1.0)

const int G = 3;
const int MOD =  998244353;
const int N = (1 << 18) + 5;

int rev[N], w[N], inv_n;

int bigMod (int a, int e, int mod)
{
    if (e == -1) e = mod - 2;
    int ret = 1;
    while (e)
    {
        if (e & 1) ret = (ll) ret * a % mod;
        a = (ll) a * a % mod;
        e >>= 1;
    }
    return ret;
}

void prepare (int &n)
{
    int sz = abs(31 - __builtin_clz(n));
    int r = bigMod(G, (MOD - 1) / n, MOD);
    inv_n = bigMod(n, MOD - 2, MOD), w[0] = w[n] = 1;
    for (int i = 1; i < n; ++i) w[i] = (ll) w[i - 1] * r % MOD;
    for (int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
}

void ntt (int *a, int n, int dir)
{
    for (int i = 1; i < n - 1; ++i)
    {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int m = 2; m <= n; m <<= 1)
    {
        for (int i = 0; i < n; i += m)
        {
            for (int j = 0; j < (m >> 1); ++j)
            {
                int &u = a[i + j], &v = a[i + j + (m >> 1)];
                int t = (ll) v * w[dir ? n - n / m * j : n / m * j] % MOD;
                v = u - t < 0 ? u - t + MOD : u - t;
                u = u + t >= MOD ? u + t - MOD : u + t;
            }
        }
    }
    if (dir) for (int i = 0; i < n; ++i) a[i] = (ll) a[i] * inv_n % MOD;
}

int f_a[N], f_b[N];

vector <int> multiply (vector <int> a, vector <int> b)
{
    int sz = 1, n = a.size(), m = b.size();
    while (sz < n + m - 1) sz <<= 1;
    prepare(sz);
    for (int i = 0; i < sz; ++i) f_a[i] = i < n ? a[i] : 0;
    for (int i = 0; i < sz; ++i) f_b[i] = i < m ? b[i] : 0;
    ntt(f_a, sz, 0);
    ntt(f_b, sz, 0);
    for (int i = 0; i < sz; ++i) f_a[i] = (ll) f_a[i] * f_b[i] % MOD;
    ntt(f_a, sz, 1);
    return vector <int> (f_a, f_a + n + m - 1);
}

vector<int>v;
ll modv[100005];
vector<long long> divideAndConqure(int l, int r)
{
    if (l == r)
    {
        vector<long long> k = {1,modv[ v[l]]};
        return k;
    }
    int mid = (l + r) >> 1;
    vector<long long> x = divideAndConqure(l, mid);
    vector<long long> y = divideAndConqure(mid + 1, r);
    return multiply(x, y);
}


main()
{
    for(ll x1=1; x1<=100001; x1++)
    {
        modv[x1]=(bigMod(2ll, x1, MOD) - 1ll + MOD) %MOD;
    }

    int ttt;

    scanf("%lld",&ttt);

    for(int ca=1; ca<=ttt; ca++)
    {
        int i,n,m,j,k,l;

        scanf("%lld %lld",&n,&k);

        int cnt[n+4]= {0ll};

        for(i=0; i<n; i++)
        {
            scanf("%lld",&m);
            cnt[m]++;
        }

        v.clear();

        for(i=1; i<=n; i++)
        {
            if(cnt[i])
            {
                v.push_back(cnt[i]);
            }
        }

        ll sz1=v.size()-1;

        vector<long long>ansvector = divideAndConqure(0,sz1);

        ll ans=0;

        ll sz=ansvector.size();

        if(sz>k)
        {
            for(i=k; i<sz; i++)
            {
                ans+=ansvector[i];
                if(ans>=MOD) ans-=MOD;
            }
        }

        printf("Case %lld: %lld\n",ca,ans);
    }

    get_lost_idiot;
}