QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#589576 | #8717. 骰子 | tarjen# | AC ✓ | 3050ms | 36460kb | C++20 | 4.7kb | 2024-09-25 18:39:08 | 2024-09-25 18:39:08 |
Judging History
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