Ideone.com

fork download

copy

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
 
using namespace std;
 
typedef long long ll;
 
mt19937 rnd(228);
 
const int N = 1e6 + 1;
const int MOD = 998244353;
 
inline int add(int a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
 
inline int mul(int a, int b)
{
    return (a * (ll) b) % MOD;
}
 
inline int bin(int a, int n)
{
    int res = 1;
    while (n)
    {
        if (n % 2 == 0)
        {
            a = mul(a, a);
            n /= 2;
        }
        else
        {
            res = mul(res, a);
            n--;
        }
    }
    return res;
}
 
int fact[N];
int rfact[N];
 
int A(int n, int k)
{
    return mul(fact[n], rfact[n - k]);
}
 
int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    fact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = mul(fact[i - 1], i);
    }
    rfact[N - 1] = bin(fact[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
    {
        rfact[i] = mul(rfact[i + 1], i + 1);
    }
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector <int> a(n);
        vector <int> cnt(n + 1);
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            cnt[a[i]]++;
        }
        int ans = 1;
        for (int i = 1; i <= n; i++)
        {
            if (cnt[i] % i)
            {
                ans = 0;
            }
            else
            {
                for (int j = 0; j < cnt[i]; j += i)
                {
                    ans = mul(ans, A(cnt[i] - j - 1, i - 1));
                }
            }
        }
        cout << ans << '\n';
    }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPHRpbWUuaD4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHVub3JkZXJlZF9zZXQ+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8c3N0cmVhbT4KIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwogCm10MTk5Mzcgcm5kKDIyOCk7CiAKY29uc3QgaW50IE4gPSAxZTYgKyAxOwpjb25zdCBpbnQgTU9EID0gOTk4MjQ0MzUzOwogCmlubGluZSBpbnQgYWRkKGludCBhLCBpbnQgYikKewogICAgYSArPSBiOwogICAgaWYgKGEgPj0gTU9EKSBhIC09IE1PRDsKICAgIHJldHVybiBhOwp9CiAKaW5saW5lIGludCBtdWwoaW50IGEsIGludCBiKQp7CiAgICByZXR1cm4gKGEgKiAobGwpIGIpICUgTU9EOwp9CiAKaW5saW5lIGludCBiaW4oaW50IGEsIGludCBuKQp7CiAgICBpbnQgcmVzID0gMTsKICAgIHdoaWxlIChuKQogICAgewogICAgICAgIGlmIChuICUgMiA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgYSA9IG11bChhLCBhKTsKICAgICAgICAgICAgbiAvPSAyOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICByZXMgPSBtdWwocmVzLCBhKTsKICAgICAgICAgICAgbi0tOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiByZXM7Cn0KIAppbnQgZmFjdFtOXTsKaW50IHJmYWN0W05dOwogCmludCBBKGludCBuLCBpbnQgaykKewogICAgcmV0dXJuIG11bChmYWN0W25dLCByZmFjdFtuIC0ga10pOwp9CiAKaW50IG1haW4oKQp7CiNpZmRlZiBPTlBDCiAgICBmcmVvcGVuKCJhLmluIiwgInIiLCBzdGRpbik7CiAgICBmcmVvcGVuKCJhLm91dCIsICJ3Iiwgc3Rkb3V0KTsKI2VuZGlmCiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBmYWN0WzBdID0gMTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgTjsgaSsrKQogICAgewogICAgICAgIGZhY3RbaV0gPSBtdWwoZmFjdFtpIC0gMV0sIGkpOwogICAgfQogICAgcmZhY3RbTiAtIDFdID0gYmluKGZhY3RbTiAtIDFdLCBNT0QgLSAyKTsKICAgIGZvciAoaW50IGkgPSBOIC0gMjsgaSA+PSAwOyBpLS0pCiAgICB7CiAgICAgICAgcmZhY3RbaV0gPSBtdWwocmZhY3RbaSArIDFdLCBpICsgMSk7CiAgICB9CiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkKICAgIHsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbjsKICAgICAgICB2ZWN0b3IgPGludD4gYShuKTsKICAgICAgICB2ZWN0b3IgPGludD4gY250KG4gKyAxKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGNpbiA+PiBhW2ldOwogICAgICAgICAgICBjbnRbYVtpXV0rKzsKICAgICAgICB9CiAgICAgICAgaW50IGFucyA9IDE7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGNudFtpXSAlIGkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGFucyA9IDA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IGNudFtpXTsgaiArPSBpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGFucyA9IG11bChhbnMsIEEoY250W2ldIC0gaiAtIDEsIGkgLSAxKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCBhbnMgPDwgJ1xuJzsKICAgIH0KfQog

Time limit exceeded #stdin #stdout 5s 10952KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/TgOyw7

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language