QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589249#8717. 骰子tarjen#TL 0ms4156kbC++204.1kb2024-09-25 16:53:172024-09-25 16:53:28

Judging History

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

  • [2024-09-25 16:53:28]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4156kb
  • [2024-09-25 16:53:17]
  • 提交

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;
struct Node{
    int l,r;
    vector<ll> res;  
};
struct SegmentTree{
    Node a[maxn*4];
    void pushup(int i){
        if(a[i].l==a[i].r)return;
        a[i].res=a[i*2].res+a[i*2+1].res;
    }
    void build(int i,int l,int r){
        a[i].l=l,a[i].r=r;
        if(l==r){
            a[i].res.resize(m+1);
            for(int j=0;j<=m;j++)cin>>a[i].res[j]; 
        }
        if(l>=r)return;
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        pushup(i);
    }
    vector<ll> query(int i,int l,int r){
        if(a[i].l>=l&&a[i].r<=r){
            return a[i].res;
        }
        if(a[i*2].r<l)return query(i*2+1,l,r);
        if(a[i*2+1].l>r)return query(i*2,l,r);    
        return query(i*2,l,r)+query(i*2+1,l,r);
    }
};
SegmentTree tri;
void add(ll &x,ll y){
    if((x+=y)>=mod)x-=mod;
}
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];
    tri.build(1,1,n);
    while(q--){
        int l,r;cin>>l>>r;
        auto p =tri.query(1,l,r);
        ll ans=0;
        for(int i=0;i<=m;i++)add(ans,p[i]*b[i]%mod);
        cout<<ans<<"\n";
    }
}

詳細信息

Test #1:

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

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: 4156kb

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: 3828kb

input:

1 1 1
604063100 57375033
742299910 257700098
1 1

output:

148903503

result:

ok 1 number(s): "148903503"

Test #4:

score: -100
Time Limit Exceeded

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: