QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470761#1436. Split in SetshyxleWA 13ms9536kbC++202.5kb2024-07-10 16:15:192024-07-10 16:15:19

Judging History

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

  • [2024-07-10 16:15:19]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:9536kb
  • [2024-07-10 16:15:19]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
const int N=1e5+5,mod=1e9+7;
ll n,k,a[N],res1,res2=1,mul[N],inv[N];
vector<int> v;
inline ll qmul(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=(a*a)%mod;b>>=1;
    }
    return ans;
}
inline void init(int _n){
    inv[0]=mul[0]=1;
    for(R int i=1;i<=_n;++i)mul[i]=mul[i-1]*i%mod;
    inv[_n]=qmul(mul[_n],mod-2);
    for(R int i=_n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
inline ll C(ll a,ll b){
    if(a<b||b<0||a<0)return 0;
    return mul[a]*inv[b]%mod*inv[a-b]%mod;
}
inline void solve(int len,int cntk,int t){
    if(t<0||!len)return;
    // cout<<len<<' '<<cntk<<'\n';
    vector<int> v1;int cnt=0;
    for(R int i=0;i<len;++i){
        v1.push_back(v.back());int kk=v.back();v.pop_back();
        if((kk>>t)&1)++cnt;
    }
    if(!cnt){
        for(R int i=0;i<len;++i){
            v.push_back(v1.back());v1.pop_back();
        }
        solve(len,cntk,t-1);
        return;
    }
    if(cnt<cntk){
        res2=(res2*mul[cntk]%mod*inv[cntk-cnt])%mod;
        for(R int i=0;i<len;++i){
            int kk=v1.back();v1.pop_back();
            if((kk>>t)&1){
                res1+=kk;--k;
            }
            else v.emplace_back(kk);
        }
        solve(v.size(),cntk-cnt,t-1);
    }else if(cnt==len&&cnt>=cntk){
        res1+=(1<<t)*(cntk);
        for(R int i=0;i<len;++i){
            int kk=v1.back();
            if((kk>>t)&1){
                kk^=(1<<t);
                v.push_back(kk);
            }
            v1.pop_back();
        }
        solve(v.size(),cntk,t-1);
    }else{
        res1+=(1<<t)*(cntk-1);
        int res=0;bool fl=0;
        for(R int i=0;i<len;++i){
            int kk=v1.back();
            if((kk>>t)&1){
                kk^=(1<<t);
                v.push_back(kk);
            }else{
                if(!fl)fl=1,res=kk;
                else res&=kk;
            }
            v1.pop_back();
        }
        v.push_back(res);
        solve(v.size(),cntk,t-1);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n>>k;init(max(n,k));
    for(R int i=1;i<=n;++i)cin>>a[i],v.emplace_back(a[i]);
    solve(n,k,30);ll sum=0;
    for(R int i=0;i<=k;++i){
        ll kk=(i%2==0?1:mod-1)*C(k,i)%mod;
        sum=(sum+kk*qmul(k-i,v.size()))%mod;
    }
    res2=(res2*sum)%mod;
    cout<<res1<<' '<<res2<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2
4 7 5

output:

11 2

result:

ok 2 tokens

Test #2:

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

input:

4 1
44 47 74 77

output:

8 1

result:

ok 2 tokens

Test #3:

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

input:

4 4
44 47 74 77

output:

242 24

result:

ok 2 tokens

Test #4:

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

input:

1000 975
633065 7087 25267 3940676 618039 1695 2043 728466935 3498 13604984 4 99 119488 151315 12 32 52705062 26815 1902279 33952 480604 390647001 60 1 12566875 7591859 6 119892 7829822 2129 4 11644639 17 33200 5330 338 2 9 6862 3781 148087 57 198 13224999 10493180 1 5755424 216 1757297 210 1002623 ...

output:

35467198613 671056390

result:

ok 2 tokens

Test #5:

score: 0
Accepted
time: 13ms
memory: 9536kb

input:

99988 19981
11771832 114 110908254 348 553453 840525742 342620766 12408 27914 2 29 4914992 79461083 133 0 44575 11059027 13445407 3508312 227 50410231 1253800 12277 201525297 39 88 20236754 417742 0 8412502 172886086 35315 144742219 211319 352393 10445 1330114 56814394 90807971 3 69704 104497 0 9176...

output:

3435071736287 430589528

result:

ok 2 tokens

Test #6:

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

input:

1000 1
275655344 268458939 268461191 268677493 268927841 297911693 268483017 269854162 282115927 398697060 270400289 268437312 268466898 268435457 268435467 291748742 268564621 268453835 269779105 268693603 268435666 386584345 268451187 268435457 268442250 268437405 268444979 268435461 268435461 268...

output:

0 1

result:

ok 2 tokens

Test #7:

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

input:

1000 3
14805621 496 64344582 2 2114 6 393783989 7458616 0 1362 55976 126045279 108353345 20049189 44 95 437 745121320 88093 3 405373757 6238 45971 1341575 1 121 2946771 15902 7578234 164 1 429590578 6739 27643 38 11 231 78030263 55 1983150 163716760 906563 446949 1 586409 3 420 2 85423631 4 73606102...

output:

1935584369 6

result:

ok 2 tokens

Test #8:

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

input:

999 953
2750440 111153032 5897842 4179 155767 26 1217 10613 33021973 2364 606 1039 2 25708532 44356 2731336 8131509 11 47 3374 10217 864014889 1335035 1626 6 1662 1926995 1413154 617430049 169873 21691 22 1157896 43 38228 9499179 1025427 922 1873902 2254 514565 13064 187 49 65341 289382656 262263674...

output:

32779801402 323536229

result:

ok 2 tokens

Test #9:

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

input:

1000 643
625292105 664789381 501359 59390402 3826 1916700 188553 25542353 117 3255788 600392 40389 227 959553533 22576447 21215 337 55920 12494719 69695 1347123 957900536 1582668 1940738 14913866 191 64 237683 6 364 39030728 0 23 3576723 1331 26293699 2 1634 1345 14969765 13 113 13 27624021 644496 1...

output:

35728055254 859009553

result:

ok 2 tokens

Test #10:

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

input:

999 864
53881381 162 296733 6281 464002 9422336 2900839 134930677 790267398 5 4754 13566793 29 3929593 13 8195474 54 43407395 10 126 2107750 6069954 87281283 837636 462057 5 10 31 1783891 5 24688892 18498742 396677 142874288 110426 130150825 5 384815 3908 4 236065713 117 2218343 3804283 182646101 5 ...

output:

31150099421 67557702

result:

ok 2 tokens

Test #11:

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

input:

1000 932
15449702 61147 2927951 459066 114406 6 32 243404061 2346088 1 11431422 5436 457840086 322 1 6 2055572 2855 2 30523 1 510 759314112 2335380 3 7 887 20 29368330 41771322 463238532 247672 45136 279744 499 900 4 2027 3 35 67 247245759 2 48110 7 20 15148 113139830 0 302812 870 2734366 7 11506972...

output:

35119427319 129193269

result:

ok 2 tokens

Test #12:

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

input:

999 821
175 57037 225 50240 440761311 3766393 4 0 39149 2319 137 2926301 1117101 928166927 171266 24745051 101092645 100165465 7500541 30118 1 272 149003 81613 466 47 38756751 3451 96 3554717 473433834 27 6929202 1493 94 9 60972 638981 10 360464986 3586673 297014 1473925 90571774 53723025 390 2214 2...

output:

34107496485 389323593

result:

ok 2 tokens

Test #13:

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

input:

1000 656
258 893 985020 262 259 357043937 13046 269 289 257 415376990 293 303 21349699 264 6332 10986 53635219 5692270 257 282217 356 305 259 845 224403462 3081 244618773 230272 428653671 24934305 6775286 22650461 256 268 13840 366581 5491960 7174525 16099 27964029 225008 2829359 1880 6695852 132239...

output:

30901843021 613472351

result:

ok 2 tokens

Test #14:

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

input:

1000 966
598 7662 16 205599 422 1949160 11388992 4 14538 3265 3620 5312455 3308 1612 835572 317539332 81 2552 316246 8 686 1986 44541 618460472 254488 6557 56495 46240563 6 34795150 2 26223984 1477 57363879 1641 2626735 2831 1 30112 95377571 18341025 552 35054 82685 1639412 117583137 20 1 56010 3381...

output:

30802651637 372287691

result:

ok 2 tokens

Test #15:

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

input:

1000 899
8 12828215 2343611 8 325786 702677184 18093754 16 46 100 1 50 7035 913 1 43761627 823587 854647 30671 234337151 3 100615086 14090819 12 83778 0 10 26 82 9001140 6822279 7299667 132 1658331 35919777 235131974 4 767 191187 395596 4 1086 19100 354 0 6603931 2080312 2 20156 623973 185 54027223 ...

output:

26166543443 367069113

result:

ok 2 tokens

Test #16:

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

input:

999 996
476178 1783726 661 59419724 406020859 493226 9347 28463 14972872 0 1342 11 11 44 512 10681475 471659 70251 17006243 147720596 0 7339279 165038496 46557 236 849 3865900 31738 281018855 266 198 5765667 3686352 6522 728 1 36 135414 334607226 53283797 12949 401252317 160 9634 106189504 2005610 1...

output:

33488159442 820131433

result:

ok 2 tokens

Test #17:

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

input:

1000 833
61741547 20 1905 541 43 1 457 1578 8 127349738 2 2 208249393 182 56972454 3 8 241 28680403 203 12409672 2943367 1316 17 3554982 25476 6738 4733093 385675 3 1604 867 270437 963016775 30551495 479526 1634 75361 861559337 217 255889256 17061659 334602 49 4 1062561 382 12079191 126742 37 6 49 5...

output:

34310887754 147968537

result:

ok 2 tokens

Test #18:

score: -100
Wrong Answer
time: 10ms
memory: 7320kb

input:

99907 2000
134218414 134221684 197183649 148833615 134217740 159844432 134217766 134220587 134217729 134224771 184225248 134328268 134217731 135416787 134218036 134217840 134217761 134217732 136229015 146153653 134246238 134219532 134217730 145300843 134223166 138322294 134217728 134234237 134217745...

output:

1232576483568 100292593

result:

wrong answer 1st words differ - expected: '1404375175408', found: '1232576483568'