QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#624174	#5019. 整数	5toubun_no_hanayome^#	0	19ms	20932kb	C++14	4.5kb	2024-10-09 15:09:08	2024-10-09 15:09:15

Judging History

你现在查看的是最新测评结果

[2024-10-09 15:09:15]
评测

测评结果：0
用时：19ms
内存：20932kb

查看

[2024-10-09 15:09:08]
提交

answer

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;

constexpr int p = 998244353;
struct mint {
    int x;
    mint(ll x = 0) : x(normalize(x % p)) {}
    static int normalize(int x) {
        if(x >= p)
            x -= p;
        else if(x < 0)
            x += p;
        return x;
    }
    constexpr int val() const {return x;}
    mint pow(int b) const {
        ll ans = 1, a = x;
        while(b) {
            if(b & 1)
                ans = ans * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return ans;
    }
    mint inv() const {
        return pow(p - 2);
    }
    mint operator - () const {
        return (mint)normalize(p - x);
    }
    friend mint& operator += (mint& lhs, const mint& rhs) {
        lhs.x = normalize(lhs.x + rhs.x);
        return lhs;
    }
    friend mint& operator -= (mint& lhs, const mint& rhs) {
        lhs.x = normalize(lhs.x - rhs.x);
        return lhs;
    }
    friend mint& operator *= (mint& lhs, const mint& rhs) {
        lhs.x = 1ll * lhs.x * rhs.x % p;
        return lhs;
    }
    friend mint& operator /= (mint& lhs, const mint& rhs) {
        assert(rhs.val());
        lhs.x = 1ll * lhs.x * rhs.inv().x % p;
        return lhs;
    }
    friend mint operator + (mint lhs, const mint& rhs) {
        lhs += rhs;
        return lhs;
    }
    friend mint operator - (mint lhs, const mint& rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend mint operator * (mint lhs, const mint& rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend mint operator / (mint lhs, const mint& rhs) {
        lhs /= rhs;
        return lhs;
    }
    friend istream& operator >> (istream& is, mint& a) {
        return is >> a.x;
    }
    friend ostream& operator << (ostream& os, const mint& a) {
        return os << a.x;
    }
    friend bool operator == (const mint& lhs, const mint& rhs) {
        return lhs.x == rhs.x;
    }
    friend bool operator != (const mint& lhs, const mint& rhs) {
        return lhs.x != rhs.x;
    }
};

const int N = 15, M = 65, MAXN = (1 << 11) + 5;
int r[N], a[MAXN], b[M];
int c[MAXN][MAXN];
mint f[M][MAXN];

bool mt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
    int n;
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> r[i];
        for(int j = r[i];j;j ^= lowbit(j))
            b[__builtin_ctz(j)] += 1 << i;
    }
    rep(i, 0, (1 << n) - 1) {
        char c;
        cin >> c;
        a[i] = c ^ 48;
    }
    rep(i, 0, (1 << n) - 1) {
        auto& c = ::c[i];
        memcpy(c, a, sizeof(a));
        rep(k, 0, n - 1) {
            if(!(i >> k & 1))
                continue;
            per(j, (1 << n) - 1, 0) {
                if(!(j >> k & 1))
                    c[j] += c[j ^ 1 << k];
            }
        }
    }
    f[60][(1 << n) - 1] = 1;
    per(i, 60, 1) {
        rep(j, 0, (1 << n) - 1) {
            if(!f[i][j].val())
                continue;
            auto c = ::c[(1 << n) - 1 ^ j];
            int k = j & b[i - 1];
            for(int l = k;;l = l - 1 & k) {
                f[i - 1][j ^ l] += f[i][j] * c[l ^ k];
                if(!l)
                    break;
            }
        }
    }
    mint ans = 0;
    rep(i, 0, (1 << n) - 1)
        ans += f[0][i];
    cout << ans << "\n";
    cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 4488kb

input:

2
557860450892773247 1006376652976945084
1001

output:

86244301

result:

wrong answer 1st numbers differ - expected: '434419861', found: '86244301'

Test #2:

score: 0

Wrong Answer

time: 1ms

memory: 6496kb

input:

2
1114627670617095929 177024338535020511
1000

output:

86244301

result:

wrong answer 1st numbers differ - expected: '1', found: '86244301'

Test #3:

score: 0

Wrong Answer

time: 1ms

memory: 4488kb

input:

2
1149393890526355314 1070730158013930700
1001

output:

86244301

result:

wrong answer 1st numbers differ - expected: '315168037', found: '86244301'

Test #4:

score: 0

Wrong Answer

time: 1ms

memory: 6312kb

input:

2
971930549804858302 431201925917048822
1001

output:

86244301

result:

wrong answer 1st numbers differ - expected: '713084688', found: '86244301'

Test #5:

score: 0

Runtime Error

input:

15
3 2 1 3 0 3 2 2 3 0 3 3 3 1 1
111100000011100110100011100000100010011010010011011101110110000011100111101101100011111100111010001010010001001111010011000000110110011111000011100100010100011010110000000010011110101111110110110100011101011101011100110000001100110111101001101001010111011000000110010...

output:

result:

Test #6:

score: 0

Runtime Error

input:

18
3 0 3 2 3 3 3 3 3 3 3 1 3 3 3 3 1 3
101101001111111010001101010111101111110111100111111011010010011000101111101100011100101111101001001010010110011001001110011101011100001100100000100011001110101101110010011011000001001001000000001001010000010100010101010101010001001110100111001001110001101000111...

output:

result:

Test #7:

score: 0

Runtime Error

input:

18
3 2 3 3 3 3 3 3 3 1 1 1 2 3 1 3 3 3
100101100011011110000000100100001001010001001000110011011111000010001110111011111010001011101101010101111111000111000011110001100111100001110100110100010101111100001001110110000000111100110011011011000110001010100110001101011011011101000110001000101101000110000...

output:

result:

Test #8:

score: 0

Wrong Answer

time: 0ms

memory: 9244kb

input:

9
774618017057897470 1150648813667465147 936044467577552867 540429591977619391 492984435788926911 706491668336975855 1148409108818935103 1152305623476461243 1151646826418395103
101100111100110000011001010001100101011001010001111000000000000001011100001010001011100110010110100001000101101101101001011...

output:

86244301

result:

wrong answer 1st numbers differ - expected: '762304370', found: '86244301'

Test #9:

score: 0

Wrong Answer

time: 2ms

memory: 10628kb

input:

9
864195661015236599 828072363954386938 215046877307787767 125420173910435807 863300627424341495 1125890835854768063 538106264396606431 1008449764986412979 1112933880000274175
1111011011101000110000110000110110111101111110011110001110010111100001010001110110111000101011110011001000101011100011011100...

output:

86244301

result:

wrong answer 1st numbers differ - expected: '91522040', found: '86244301'

Test #10:

score: 0

Wrong Answer

time: 3ms

memory: 9276kb

input:

9
1060294142652751871 270953131468627965 950114304166317032 1023152535943950935 1124721212123772879 1136030244306680786 575888989072637942 576457170017579983 1071468780714196734
10010111011101001111011010000011000000111111000001100001001110001000000000101001001101110110001001111011110111101001000000...

output:

86244301

result:

wrong answer 1st numbers differ - expected: '235859607', found: '86244301'

Test #11:

score: 0

Wrong Answer

time: 19ms

memory: 20800kb

input:

11
1044692707433249934 1008683100277431676 999797431367270367 1143631656501850799 1098790111790735245 468268805647233519 539233207094867537 414313023104679647 1113992177660166126 1150563014851263359 1146149597257104766
111100100001011011010001100111000010001101110011110101110101010110100111111011000...

output:

86244301

result:

wrong answer 1st numbers differ - expected: '238088536', found: '86244301'

Test #12:

score: 0

Wrong Answer

time: 15ms

memory: 20932kb

input:

11
1136928866896019455 954477066817884159 139540257629524991 920699090857753087 852006989960417247 557707207097472255 575228611095427007 1006976729003116287 709142041517850567 1136595818501773047 1006109764096082108
100001110101001011001100010000100000111110011110100011000011111011000001010001110001...

output:

86244301

result:

wrong answer 1st numbers differ - expected: '770640307', found: '86244301'

Test #13:

score: 0

Wrong Answer

time: 19ms

memory: 20868kb

input:

11
1152568556892716543 1152920608551467963 216135265528237819 1116892698712710517 1125524963696923135 990737955748133887 575754796832378359 959086400709851129 571809817905978127 391758946252877613 553053934827077551
100001001101100001010110011000000001110110100101011111010110001101000110111100110011...

output:

86244301

result:

wrong answer 1st numbers differ - expected: '12490130', found: '86244301'

Test #14:

score: 0

Runtime Error

input:

13
431747275278769839 792173935971856335 842168688984356222 709201683711004463 1096549254077341383 432312541824942061 423302887995576278 1152284609275166700 1150353045444060639 858881033326555901 429385610205061119 394803803773730111 792573841785221941
11101010110000000010101000000011010001110011111...

output:

result:

Test #15:

score: 0

Runtime Error

input:

13
384952197575497562 925188207794820790 819636358341950664 1008806169945307033 485498962656536575 576170342985224059 1152884825316839167 519602798379984887 1148271257506507710 864338725486642591 141147914734645085 945751520335947454 828363124049108987
10111011110011010100110001011011010100001001111...

output:

result:

Test #16:

score: 0

Runtime Error

input:

13
812148678079544783 531352737042856447 360252648370171639 827797221788122302 1076354330155122647 571657826460300281 995857311985303518 576390067592282047 573059687658290935 1134130623250689782 573953435640528550 1148043723132895167 576443122223672059
11010001100111100001101001010010100111100000010...

output:

result:

Test #17:

score: 0

Runtime Error

input:

18
557601891651940085 863281395625602303 810348831133032447 855679530581929974 1143340273566153982 1142779849869883883 495305789849593903 1141378831228050923 539285017652624765 1151477836095937523 968834653063196607 462735989800959869 567170978455011071 936570564589289083 1089862139502785535 1274543...

output:

result:

Test #18:

score: 0

Runtime Error

input:

18
35461063007254983 250722149174607860 990787107658114938 521176448595639215 1142533318210222071 848423510290851199 936184673027902967 1035761934176939767 1152921455940040799 759980081052254206 841582125096893943 1105339004669119437 1071810531808477044 1072419334446896991 1152903339507575642 131161...

output:

result:

Test #19:

score: 0

Runtime Error

input:

18
526745011001725941 995280101634205694 1150650377238908861 1152780629645981351 378291368993988607 754341611678006135 1133780828220553215 467476844077883365 998548842292821951 1125758065340935934 1074758391215161343 359069688757419477 863137999561424871 459006511440394231 856772308259666431 2832407...

output:

result:

Test #20:

score: 0

Runtime Error

input:

18
1116852845721419519 564031047050710929 1152918474977164029 288041155646291455 647954749928207825 978368260719998815 1141854864204889983 1121382897240509261 576459613035256827 1134273717606465523 1124121994315404271 714513083207720351 1001083345502337005 642993847483219627 1143878547027000662 1139...