QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589576#8717. 骰子tarjen#AC ✓3050ms36460kbC++204.7kb2024-09-25 18:39:082024-09-25 18:39:08

Judging History

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

  • [2024-09-25 18:39:08]
  • 评测
  • 测评结果:AC
  • 用时:3050ms
  • 内存:36460kb
  • [2024-09-25 18:39:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod =1e9+7;
namespace polynomial {
    typedef complex<long double> cplx;
    const long double pi = acos((long double)-1.0);
    const int len = 15, mask = (1 << len) - 1;
    struct UnitRoot {
        static vector<cplx> w;
        static vector<cplx> get_root(int n) {
            n = 1 << 32 - __builtin_clz(n);
            if (n > w.size()) {
                w.resize(n);
                for (int i = 0; i < n; i++)
                    w[i] = cplx(cos(2 * i * pi / n), sin(2 * i * pi / n));
            }
            int m = w.size() / n;
            vector<cplx> res(n);
            for (int i = 0, j = 0; i < n; i++, j += m) res[i] = w[j];
            return res;
        }
    };
    vector<cplx> UnitRoot::w;
 
    void fft(vector<cplx> &p, const vector<cplx> &w) {
        int n = w.size();
        for (int i = 1, j = 0; i < n - 1; ++i) {
            int s = n;
            do {
                s >>= 1;
                j ^= s;
            } while (~j & s);
            if (i < j) {
                swap(p[i], p[j]);
            }
        }
        for (int d = 0; (1 << d) < n; ++d) {
            int m = 1 << d, m2 = m * 2, rm = n >> (d + 1);
            for (int i = 0; i < n; i += m2) {
                for (int j = 0; j < m; ++j) {
                    auto &p1 = p[i + j + m], &p2 = p[i + j];
                    auto t = w[rm * j] * p1;
                    p1 = p2 - t;
                    p2 = p2 + t;
                }
            }
        }
    }
    vector<long long> conv(const vector<long long> &a,const vector<long long> &b) {
        vector<cplx> w = UnitRoot::get_root(a.size() + b.size() - 1);
        int n = w.size();
        vector<cplx> A(n), B(n), C(n), D(n);
        for (int i = 0; i < a.size(); ++i) A[i] = cplx(a[i] >> len, a[i] & mask);
        for (int i = 0; i < b.size(); ++i) B[i] = cplx(b[i] >> len, b[i] & mask);
        fft(A, w), fft(B, w);
        for (int i = 0; i < n; ++i) {
            int j = (n - i) % n;
            cplx da = (A[i] - conj(A[j])) * cplx(0, -0.5),db = (A[i] + conj(A[j])) * cplx(0.5, 0),dc = (B[i] - conj(B[j])) * cplx(0, -0.5),dd = (B[i] + conj(B[j])) * cplx(0.5, 0);
            C[j] = da * dd + da * dc * cplx(0, 1);D[j] = db * dd + db * dc * cplx(0, 1);
        }
        fft(C, w), fft(D, w);
        vector<long long> res(a.size() + b.size() - 1);
        for (int i = 0; i < res.size(); ++i) {
            long long da = (long long)(C[i].imag() / n + 0.5) % mod,db = (long long)(C[i].real() / n + 0.5) % mod,dc = (long long)(D[i].imag() / n + 0.5) % mod,dd = (long long)(D[i].real() / n + 0.5) % mod;
            res[i] = ((dd << (len * 2)) + ((db + dc) << len) + da) % mod;
        }
        return res;
    }
};
using namespace polynomial;
int n,m,q;
vector<ll> operator+(vector<ll> a,vector<ll> b){
    auto p=conv(a,b);
    p.resize(m+1);
    return p;
}
const int maxn=1510;
void add(ll &x,ll y){
    if((x+=y)>=mod)x-=mod;
}
struct Query{
    int l,r,id;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    vector<ll> b(m+1);
    for(int i=0;i<=m;i++)cin>>b[i];
    vector<vector<ll>> p(n+1,vector<ll>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++)cin>>p[i][j];
    }
    vector<ll> ans(q);
    vector<Query> query(q);
    for(int i=0;i<q;i++)cin>>query[i].l>>query[i].r,query[i].id=i;
    function<void(int,int,vector<Query>&)> solve =[&](int l,int r,vector<Query>&query){
        if(l==r){
            ll sum=0;
            for(int i=0;i<=m;i++)add(sum,p[l][i]*b[i]%mod);
            for(auto it:query)ans[it.id]=sum;
            return;
        }
        int mid=(l+r)/2;
        vector<vector<ll>> L{p[mid]},R{p[mid+1]};
        for(int i=mid-1;i>=l;i--){
            auto v=L.back()+p[i];
            L.emplace_back(move(v));
        }
        vector<vector<ll>> vL(L.size());
        for(int i=0;i<L.size();i++){
            vL[i].resize(m+1);
            for(int j=0;j<=m;j++){
                for(int k=0;k+j<=m;k++)add(vL[i][j],b[j+k]*L[i][k]%mod);
            }
        }
        for(int i=mid+2;i<=r;i++){
            auto v=R.back()+p[i];
            R.emplace_back(move(v));
        }
        vector<Query> ql,qr;
        for(auto &it:query){
            if(it.r<=mid)ql.push_back(it);
            else if(it.l>mid)qr.push_back(it);
            else{
                ll sum=0;
                for(int i=0;i<=m;i++)add(sum,vL[mid-it.l][i]*R[it.r-mid-1][i]%mod);
                ans[it.id]=sum;
            }
        }
        solve(l,mid,ql);
        solve(mid+1,r,qr);
    };
    solve(1,n,query);
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3

output:

3
1
0

result:

ok 3 number(s): "3 1 0"

Test #2:

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

input:

3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3

output:

2
1
0
3
1
2

result:

ok 6 numbers

Test #3:

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

input:

1 1 1
604063100 57375033
742299910 257700098
1 1

output:

148903503

result:

ok 1 number(s): "148903503"

Test #4:

score: 0
Accepted
time: 3050ms
memory: 36460kb

input:

1500 200 600000
253665324 876103781 804024983 929290295 908790466 176299158 528078340 696679927 416465140 509641654 705083449 361711737 250659645 735832780 35321360 383752049 203979021 178832532 785212637 514502839 169840231 65809146 504755349 516829442 382478309 901925498 142312128 782336477 741339...

output:

66394849
858043015
290088512
433850735
16359498
544692508
495705795
390858705
334940115
441003348
589429674
891250455
147055038
949270774
782296292
854444995
608076278
772991067
609961969
3444634
534397763
659524291
384815421
329963211
259265811
214554716
662015873
465616975
355211926
398786302
7484...

result:

ok 600000 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 4300kb

input:

10 200 50
370772932 487085918 522119313 202271129 795784341 241675432 84696649 6593125 142447175 433043082 912818145 541105733 352679271 713064369 909540704 642928848 262928894 910729006 19720645 257900859 152127142 466747981 548396756 424075620 112979677 6097940 549613699 409134160 673872615 423969...

output:

95478933
40420846
949457584
785743027
889119897
679023045
369149401
975015432
354462393
485444538
29208842
586846064
186163820
22554968
824615211
569553393
744645623
242702753
632410029
205596998
61853702
489103277
732828674
100756683
141691367
282384748
410111173
962211860
167960231
479439671
24188...

result:

ok 50 numbers

Test #6:

score: 0
Accepted
time: 2885ms
memory: 31080kb

input:

1451 196 495733
867638655 902055413 105294111 137664336 471592456 918420578 125072731 308929978 27685746 452519696 98422383 706168360 78074387 292091353 618373494 369467100 162485874 836155739 298771673 885513404 838310084 906054277 607746923 87340077 246700830 757296916 704582501 989205453 31137463...

output:

460690386
278678842
53059823
742261043
218023681
845226442
807934157
947218276
439209786
134749344
333062838
85472333
716670499
918798477
869889873
62065687
294021428
402449069
219660955
196254975
555611425
92638506
562044910
38568438
356602242
709735280
604757128
569518126
36515714
351120221
532138...

result:

ok 495733 numbers

Test #7:

score: 0
Accepted
time: 3023ms
memory: 34148kb

input:

1500 200 540000
223660186 89468677 759079474 404830014 979472869 83267050 83563367 677675529 859956529 155987948 353693543 77500819 86016820 650321973 494266976 680564693 452260610 995412525 340962913 500500716 566751189 684928139 427671993 89692208 6597269 333294046 339922474 694930232 485180083 51...

output:

0
0
336294876
467089346
0
982024564
0
818667512
696589964
622577755
0
0
0
785586193
0
0
944327932
0
509627964
843415527
969890452
0
937503991
770845465
962611688
193026222
724721775
811172009
778901622
609135235
0
358665248
124966698
551642216
918648252
0
641301974
839720389
93459623
241080994
21718...

result:

ok 540000 numbers

Test #8:

score: 0
Accepted
time: 2871ms
memory: 33920kb

input:

1494 170 600000
401180116 688567218 62843723 545029957 206920560 177345580 769762918 829272212 462277941 753515932 302840629 970657356 916220281 213592777 862002384 190527510 91750240 877239697 471954197 940033161 742402869 632372244 244285549 458360335 642939560 70979153 205902868 36837822 26680432...

output:

464045721
885048076
0
492090219
468239489
828817640
242844948
875727270
0
100655424
980764960
985325822
80971612
843425086
674298027
575445303
501679520
629174460
132121609
311125954
897030977
676292437
206048315
0
327770406
934980265
136154222
0
253128449
293936905
0
374315641
7827333
342855032
631...

result:

ok 600000 numbers

Extra Test:

score: 0
Extra Test Passed