QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416481 | #8717. 骰子 | ucup-team052 | TL | 1ms | 5728kb | C++23 | 2.3kb | 2024-05-21 21:33:45 | 2024-05-21 21:33:45 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 1000000007
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int add(int x,int y,int z) {return add(add(x,y),z);}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1ULL*x*y%mod;}
inline int mul(int x,int y,int z) {return mul(mul(x,y),z);}
#define inc(x,y) x=add(x,y)
#define dec(x,y) x=sub(x,y)
int qpow(int x,int y)
{
int ans=1;
while(y)
{
if(y&1) ans=mul(ans,x);
x=mul(x,x);
y>>=1;
}
return ans;
}
int Inv(int x){return qpow(x,mod-2);}
#define M 205
#define N 1505
int a[N][M],w[M],n,m,Q;
int bad[N],sbad[N];
int pre[N][M],preinv[N][M];
void getinv(int a[],int b[],int m)
{
assert(a[0]!=0);
b[0]=Inv(a[0]);
for(int i=1;i<=m;i++)
{
__int128 sum=0;
for(int j=0;j<i;j++) sum+=1ULL*b[j]*a[i-j];
b[i]=sum*(mod-b[0])%mod;
}
}
signed main()
{
cin>>n>>m>>Q;
for(int i=0;i<=m;i++) w[i]=read();
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++) a[i][j]=read()%mod;
while(a[i][bad[i]]==0) bad[i]++;
sbad[i]=sbad[i-1]+bad[i];
for(int j=0;j<=m-bad[i];j++) a[i][j]=a[i][j+bad[i]];
}
pre[0][0]=1,preinv[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
__int128 sum=0;
for(int k=0;k<=j;k++) sum+=1ULL*pre[i-1][k]*a[i][j-k];
pre[i][j]=sum%mod;
}
getinv(pre[i],preinv[i],m);
}
// for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) printf("%d%c",pre[i][j]," \n"[j==m]);
while(Q--)
{
int l=read(),r=read();
int ned=sbad[r]-sbad[l-1];
int ans=0;
for(int i=0;i<=m-ned;i++)
{
__int128 coef=0;
for(int j=0;j<=i;j++) coef+=1ULL*pre[r][j]*preinv[l-1][i-j];
ans=add(ans,coef*w[i+ned]%mod);
}
printf("%d\n",ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5728kb
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: 1ms
memory: 3636kb
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: 1ms
memory: 3680kb
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...