3 months ago

Mayank • 90

Varanasi

2nd and 3rd one ??

7 weeks ago

mk390270 • 50

Patna

//​1ST Problem Solution


#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i, n) for (i = 0; i < n; i++)
#define Fo(i, k, n) for (i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long
#define si(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define ss(s) scanf("%s", s)
#define pi(x) printf("%d\n", x)
#define pl(x) printf("%lld\n", x)
#define ps(s) printf("%s\n", s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
void cout_v(vector<int> &v)
{
    for (auto it : v)
        cout << it << " ";
}
int rng(int lim)
{
    uniform_int_distribution<int> uid(0, lim - 1);
    return uid(rang);
}
const int mod = 1000000007;
ll inv(ll i)
{
    if (i == 1)
        return 1;
    return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;
}

ll mod_mul(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    return (((a * b) % mod) + mod) % mod;
}

ll mod_add(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    return (((a + b) % mod) + mod) % mod;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll ceil_div(ll a, ll b) { return a % b == 0 ? a / b : a / b + 1; }

int mpow(int base, int exp)
{
    base %= mod;
    int result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = ((ll)result * base) % mod;
        base = ((ll)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

/*

1. Think Greedy
2. Think Brute Force
3. Think solution in reverse order
4. Think DP [ check constraints carefully ]
5. Check base cases for DP and prove solution for Greedy
6. Think Graph

*/
// #@copyrightMUKESH
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////*
const int N = 1e4;
int dp[N + 1][(1 << 11) + 1];
int fun(int mask, int ind, int n, vi &masks)
{
    if (mask == ((1 << 11) - 1))
        return 1;
    if (ind == n)
    { 
        if (mask)
            return 1;
        return 0;
    }
    if (dp[ind][mask] != -1)
        return dp[ind][mask];
    bool ok = false;
    for (int i = 0; i < 10; i++)
    {
        if (((mask >> i) & 1) && ((masks[ind] >> i) & 1))
            ok = true;
    }
    if(masks[ind]==(1<<11))ok=true;
    int ans = 0;
    if (ok)
    {
        ans = mod_add(ans, fun(mask, ind + 1, n, masks));
    }
    else
    {
        ans = mod_add(ans, fun(mask ^ masks[ind], ind + 1, n, masks) + fun(mask, ind + 1, n, masks));
    }
    return dp[ind][mask] = ans;
}
void solve()
{
    memset(dp, -1, sizeof(dp));
    int n;
    cin >> n;
    int i;
    vi a(n);
    fo(i, n) cin >> a[i];
    vi primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    vi masks(n + 1, (1 << 11));
    fo(i, n)
    {
        int t = a[i];

        vi visited(31, 0);

        bool ok = false;
        while (t != 1)
        {
            int first_prime = 0;
            for (auto it : primes)
            {
                if (t % it == 0)
                {
                    first_prime = it;
                    break;
                }
            }

            if (first_prime == 0)
            {
                ok = true;
                break;
            }
            visited[first_prime]++;
            t /= first_prime;
        }
        for (auto it : primes)
        {
            if (visited[it] > 1)
                ok = true;
        }
        if (!ok)
        {
            int mask = 0;
            for (int j = 0; j < 10; j++)
            {
                if (visited[primes[j]])
                    mask += (1 << j);
            }
            masks[i] = mask;
        }
    }

    cout << fun(0, 0, n, masks) << "\n";
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

​