QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119737#3543. Random XORznk2373065134AC ✓762ms5092kbC++141.1kb2023-07-05 16:52:452023-07-05 16:52:46

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 16:52:46]
  • Judged
  • Verdict: AC
  • Time: 762ms
  • Memory: 5092kb
  • [2023-07-05 16:52:45]
  • Submitted

answer

#include <stdio.h>
typedef long long ll;

const int MAXN = 1e5 + 10, MOD = 1e9 + 7;
int n, P, a[MAXN];
ll ans, f[MAXN][4];

int Pow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = ((ll)res * a) % MOD;
        b >>= 1;
        a = ((ll)a * a) % MOD;
    }
    return res;
}

int main() {
    int X, Y;
    scanf("%d%d%d", &n, &X, &Y);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    P = ((ll)X * Pow(Y, MOD - 2)) % MOD;
    for (int i = 0; i <= 30; ++i) {
        for (int j = 0; j <= 30; ++j) {
            for (int x = 1; x <= n; ++x) {
                f[0][0] = 1, f[0][1] = f[0][2] = f[0][3] = 0;
                int u = (((a[x] >> i) & 1) << 1) | ((a[x] >> j) & 1);
                for (int y = 0; y < 4; ++y) {
                    f[x][y] = ((1 - P) * f[x - 1][y] + P * f[x - 1][u ^ y]) % MOD;
                }
            }
            ans = (ans + ((f[n][3] * (1 << i)) % MOD) * (1 << j)) % MOD;
        }
    }
    ans = (ans + MOD) % MOD;
    printf("%lld", ans);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 1616kb

input:

3 1 2
2 8 10

output:

42

result:

ok 1 number(s): "42"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1520kb

input:

20 149314548 487620059
432702034 581964972 754852845 255229981 100591153 838128852 617432940 919463343 976203909 965969363 743736208 106487494 170972920 448509027 196876392 455927876 935162409 454116240 481242309 486057486

output:

199088783

result:

ok 1 number(s): "199088783"

Test #3:

score: 0
Accepted
time: 0ms
memory: 1740kb

input:

20 506123105 660746025
283335540 259637102 341366840 389703578 31673632 572458173 934525210 932728573 541451488 137448904 201787157 626351768 580707561 3783224 775276489 77444544 704196403 64080662 240847089 223243498

output:

940529380

result:

ok 1 number(s): "940529380"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1860kb

input:

20 742272517 833871991
547829782 933513975 514020106 110316440 548895383 716852965 546584740 240961064 811731805 13961185 659838114 851248775 699270198 559057429 62504574 990133223 768197665 969012359 291623872 374290245

output:

154933733

result:

ok 1 number(s): "154933733"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

20 485512290 712030685
398463289 902358108 690468637 240994773 69912392 156215018 449816275 959259034 376979384 181645470 117889063 367317778 109004832 114331626 640904671 611649891 537231659 165116045 47433388 525336991

output:

774024491

result:

ok 1 number(s): "774024491"

Test #6:

score: 0
Accepted
time: 0ms
memory: 1748kb

input:

20 500270982 590189379
957924798 871202242 863121903 375468369 292166875 595577078 61875805 681352260 233398966 58157750 867112023 592214784 518739473 83466558 338198227 229371296 601232921 775080474 98210171 672588474

output:

739624199

result:

ok 1 number(s): "739624199"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

100 171070078 509294025
594553528 566309265 705832458 585236063 396646402 313940406 929409876 747999710 326501601 527377660 179617974 230134508 417657603 761961673 328027347 187393545 582507310 410407852 343346452 423598349 136088456 977326863 849776995 979531651 337690042 594065795 525165097 270250...

output:

130801779

result:

ok 1 number(s): "130801779"

Test #8:

score: 0
Accepted
time: 1ms
memory: 1596kb

input:

100 6340934 977387263
154015031 949014134 587313720 719709660 622696149 753302466 541469406 761264940 891749187 698857208 637668931 749998783 831187508 317235870 611460176 513942952 351541305 606511546 394123236 865817100 64241900 934720738 138765108 421159254 147286813 977430619 160913006 324667270...

output:

85500519

result:

ok 1 number(s): "85500519"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

100 63556032 855545957
4648538 917858268 173827715 145355254 139917893 192664519 563594408 69497432 456996765 280402221 95719880 266067786 945954881 286370802 898688268 426631624 120575299 511443236 149932751 16863840 578534616 597147345 841613963 862786864 251850852 651967440 87832919 84116780 9211...

output:

94840149

result:

ok 1 number(s): "94840149"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1744kb

input:

100 687018047 733704651
974175518 591735133 346480981 865968122 362172377 632026579 175653938 787795401 22244344 451881770 553770836 785932060 359484779 841645007 182121090 753181032 184576561 121407658 909537538 167910586 801655329 554541220 130602076 595586471 61447623 326504261 723580836 13853355...

output:

929784720

result:

ok 1 number(s): "929784720"

Test #11:

score: 0
Accepted
time: 1ms
memory: 1752kb

input:

100 388541989 906830617
824809025 560579267 522929512 291613716 883189392 776421371 787713476 801060631 292524661 619566054 11821786 302001063 64186681 396919204 760521186 665869704 953610562 317511351 960314321 610129337 24776034 216967827 419590196 742246814 871044401 709869085 945468017 897983076...

output:

973512633

result:

ok 1 number(s): "973512633"

Test #12:

score: 0
Accepted
time: 8ms
memory: 3660kb

input:

1000 78770515 126874305
128270545 615680173 189939115 453675559 464157783 173046628 76061430 787820317 730179210 325393795 940049054 527670797 961966063 643466577 385481149 870627835 661392925 249752152 68984377 948456639 578755692 313639171 316656557 530824584 655383944 336371044 57914502 37767649 ...

output:

690206828

result:

ok 1 number(s): "690206828"

Test #13:

score: 0
Accepted
time: 5ms
memory: 1692kb

input:

1000 89670875 300000271
683936791 584524307 71420377 588149156 981379534 317441420 688120968 801085547 459520 496873343 103132736 338707069 785561432 198740774 373946709 197177235 725394187 445855846 119761161 99503378 506909136 976065785 310677409 263624191 464980715 715940604 693662418 797217166 4...

output:

274798406

result:

ok 1 number(s): "274798406"

Test #14:

score: 0
Accepted
time: 8ms
memory: 3644kb

input:

1000 359820247 473126237
534570298 553368440 247868908 308762018 207429274 756803480 300180498 814350778 856879110 664557628 852355696 563604075 490263334 754014978 661174802 109865907 494428181 55820267 170537944 250550125 21201845 933459660 599665529 705251801 274577486 99305420 329410328 55666667...

output:

681702278

result:

ok 1 number(s): "681702278"

Test #15:

score: 0
Accepted
time: 8ms
memory: 1500kb

input:

1000 527906164 646252203
94031800 522212574 420522174 734407618 429683757 196165533 912240036 827616008 422126688 836037177 310406645 374640346 605030707 14321907 239574891 436415314 558429443 960751964 635175463 397801608 244322558 595886268 888653649 146879405 379141525 773842248 256330241 6110834...

output:

667133821

result:

ok 1 number(s): "667133821"

Test #16:

score: 0
Accepted
time: 8ms
memory: 1624kb

input:

1000 333842240 524410897
649698046 904917443 302003437 163848476 950700773 635527593 520504302 840881238 692407006 417582189 473490333 599537352 18560605 278424108 526802984 349103987 327463437 156855651 685952246 548848354 467443270 262108139 882674501 998572486 188738296 448379069 892078157 370532...

output:

481911746

result:

ok 1 number(s): "481911746"

Test #17:

score: 0
Accepted
time: 77ms
memory: 1884kb

input:

10000 333863224 974634855
990300844 287272648 745994944 189092861 552028875 912149529 55984648 14630290 454671195 281139835 473430703 919564213 267679526 392338937 296046283 127937158 254600585 554075046 229645952 449582193 946543923 209405659 438651362 343521732 584499712 671544244 382311151 326664...

output:

835938208

result:

ok 1 number(s): "835938208"

Test #18:

score: 0
Accepted
time: 77ms
memory: 3904kb

input:

10000 36997324 442728087
549762347 964944784 918648210 323566458 774283358 351511582 373076918 322862788 19918773 448824120 636514391 849493951 386242163 947613141 874446380 454486565 318601848 459006735 280422736 891800943 169664628 871832273 727639482 490182075 394096483 54909061 18059061 37825524...

output:

951708210

result:

ok 1 number(s): "951708210"

Test #19:

score: 0
Accepted
time: 76ms
memory: 1928kb

input:

10000 121001695 320886781
400395853 638821650 95096734 44179320 291505102 495906374 690169187 336128018 290199091 325336401 94565340 660530222 795976804 502887338 161674465 367175237 796463845 360143161 331199519 42847683 683957344 534258880 16627595 222981682 498660522 434478621 239946242 137704751...

output:

874666460

result:

ok 1 number(s): "874666460"

Test #20:

score: 0
Accepted
time: 77ms
memory: 3544kb

input:

10000 60016921 199045475
956062099 607665783 976578004 469824920 517554850 230235695 302228718 54425981 146618673 201848681 552616297 885427229 205711438 472022270 445107294 693724645 565497839 265074851 87009035 193894430 202045318 200480752 719476450 369642024 308257293 817843445 580726890 8971542...

output:

368722749

result:

ok 1 number(s): "368722749"

Test #21:

score: 0
Accepted
time: 76ms
memory: 1940kb

input:

10000 228335185 372171441
515523602 281542649 149231263 899265785 34776594 374630487 619320987 362658479 711866259 373328230 301839250 696463500 324274075 27296467 732335386 606413317 334531833 875039280 551646553 341145912 425166030 862907366 713497302 811269634 117854064 787347534 507646804 951571...

output:

366092391

result:

ok 1 number(s): "366092391"

Test #22:

score: 0
Accepted
time: 758ms
memory: 5092kb

input:

100000 10761862 100072374
334639013 66346573 909401708 551571510 821200568 644940356 95805255 709479902 838826602 742808383 62138989 873938137 149184430 449792738 274247834 206822772 93944885 279712971 459536974 183421426 282856231 672489964 989944303 366248366 323009696 913121652 149828308 71195153...

output:

423609138

result:

ok 1 number(s): "423609138"

Test #23:

score: 0
Accepted
time: 758ms
memory: 4924kb

input:

100000 128118927 273198340
185272519 449051441 82054968 272184372 633389580 789335148 117930257 427777865 109106912 914287932 520189945 98835136 558919071 710099674 557680663 123306708 571806882 184644660 219141753 334468172 505976944 338711835 278932416 807875977 427573735 292691205 76748221 471401...

output:

565315062

result:

ok 1 number(s): "565315062"

Test #24:

score: 0
Accepted
time: 761ms
memory: 5064kb

input:

100000 80094709 151357034
35906026 417895575 963536237 111690700 564472059 523664469 729989794 736010363 674354498 790800213 978240901 614904146 677481708 974201874 844908755 741028120 635808144 380748354 269918537 485514919 729097656 1138442 272953268 954536319 237170506 971023297 417528870 5258178...

output:

813278878

result:

ok 1 number(s): "813278878"

Test #25:

score: 0
Accepted
time: 762ms
memory: 5052kb

input:

100000 1273945 324483001
300400268 91772440 845017500 537336301 81693804 668059261 342049325 749275593 944634816 253451758 436291850 839801152 87216342 529476071 423308844 362544788 404842138 990712783 320695320 636561666 538357633 663565056 561941388 687335926 46767277 645560118 639416051 285267330...

output:

409582215

result:

ok 1 number(s): "409582215"

Test #26:

score: 0
Accepted
time: 759ms
memory: 5080kb

input:

100000 198587255 497608967
856066513 60616574 17670759 257949163 598915555 402388582 950313598 467573555 804849662 129964039 894342807 650837424 496950983 84750268 415569669 980266199 173876132 186816470 76504836 783813149 761478345 620958931 850929508 128963529 151331317 25129671 275163960 44716840...

output:

292983352

result:

ok 1 number(s): "292983352"