Submission #66811639

---

Source Code Expand

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using ld = long double;

typedef tree<
        int,
        null_type,
        less<int>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;

#define mp make_pair
mt19937 rnd(time(0));

// 1. Overload the << operator for std::pair
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    os << p.first << ' ' << p.second << "|";
    return os;
}

// 2. Simple trait to detect if a type is a container
template<typename T, typename = void>
struct is_container : false_type {};

// Specialization: If T has begin() and end(), it's a container
template<typename T>
struct is_container<T, void_t<
        decltype(std::declval<T>().begin()),
        decltype(std::declval<T>().end())
>> : true_type {};

// 3. Generic print function
template<typename T>
void print(const T& element) {
    if constexpr (is_container<T>::value) {
        for(const auto& e : element) {
            print(e); // Recursive call for nested containers
        }
        cout << endl; // Newline after printing a container
    }
    else {
        cout << element << ' '; // Print non-container elements
    }
}


//const int MOD = 1'000'000'007;
const int MOD = 998'244'353;

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=MOD) s-=MOD;
    return s;
}

int sub(int a, int b) {
    int s = (a+MOD-b);
    if (s>=MOD) s-=MOD;
    return s;
}

int po(int a, ll deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, MOD-2);
}

int LIM = 1'005;
vector<int> facs, invfacs, invs, min_prime, phi, mu;
//vector<vector<int>> divisors(LIM);

void init_nt(int lim = -1)
{
    if (lim != -1) LIM = lim;
    facs.resize(LIM); invfacs.resize(LIM); invs.resize(LIM); mu.resize(LIM);

    facs[0] = 1;
    for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
    invfacs[LIM-1] = inv(facs[LIM-1]);
    for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
    for (int i = 1; i<LIM; i++) invs[i] = mul(invfacs[i], facs[i-1]);

    min_prime = vector<int>(LIM, -1);
    phi = vector<int>(LIM, 1);

    for (int i = 2; i<LIM; i++) if (min_prime[i] == -1)
        {
            min_prime[i] = i;
            phi[i] = i-1;
            for (int j = i; j<LIM; j+=i)
            {
                if (min_prime[j] == -1) min_prime[j] = i;
            }
        }

    for (int i = 2; i<LIM; i++) if (phi[i] == 1)
        {
            int p = min_prime[i];
            if ((i/p)%p == 0) phi[i] = phi[i/p]*p;
            else phi[i] = phi[i/p]*(p-1);
        }

    mu[1] = 1;
    for (int i = 2; i<LIM; i++)
    {
        if ((i/min_prime[i])%min_prime[i] == 0) mu[i] = 0;
        else mu[i] = -mu[i/min_prime[i]];
    }

    /*for (int i = 2; i<LIM; i++) if (min_prime[i] == i)
    {
        for (int j = i; j<LIM; j+=i) divisors[j].push_back(i);
    }*/
}

int C(int n, int k)
{
    if (n<k) return 0;
    if (n<0 || k<0) return 0;
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}

int C1(int n, int k)
{
    int ans = 1;
    for (int i = n; i>=n-k+1; i--) ans = mul(ans, i);
    for (int i = 1; i<=k; i++) ans = mul(ans, invs[i]);
    return ans;
}

void solve()
{
    int n, m; cin>>n>>m;

    int deg = po(2, m);
    //a[0] = 0
    int ans = 0;

    int K = 5;
    vector<vector<int>> calc(K, vector<int>(K)); //calc[tot][required]

    for (int tot = 1; tot<K; tot++)
        for (int req = 0; req<=tot; req++)
        {
            calc[tot][req] = po(tot, n-1);
            for (int take = 0; take<req; take++)
            {
                calc[tot][req] = sub(calc[tot][req], mul(calc[tot-(req - take)][take], C(req, take)));
            }
        }

    /*vector<int> calc(5);
    calc[0] = 1;
    for (int i = 1; i<5; i++)
    {
        calc[i] = po(i+1, n-1);
        for (int j = 0; j<i; j++)
        {
            calc[i] = sub(calc[i], mul(calc[j], C(i, j)));
        }
    }*/


    //Case 1: 0 2bits

    ans = add(ans, po(m+1, n-1));

    //Case 2: 0, a^b, a^c, b^c

    int ways = C1(m, 3);
    ans = add(ans, mul(ways, calc[4][3]));

    //In remaining cases all 2bits have common bit

    //Case 3: exactly 1 2bit: 0, a^b, a, b

    ways = C1(m, 2);
    ans = add(ans, mul(ways, calc[4][1]));

    //Case 4: multiple 2bits with same bit a: a^whatever, possibly a

    ways = C1(m, 1);

    ans = add(ans, mul(ways, po(m+1, n-1))); //All of them, but includes case when 0 or 1

    //Subbing 0
    ans = sub(ans, mul(ways, calc[2][0]));

    //Subbing 1
    ans = sub(ans, mul(mul(m, m-1), calc[3][1]));

    ans = mul(ans, deg);
    cout<<ans<<endl;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    init_nt();

    int t; cin>>t;
    while (t--) solve();
}

Submission Info

Judge Result