QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608972 | #8717. 骰子 | UESTC_OldEastWest | ML | 1ms | 7772kb | C++17 | 2.3kb | 2024-10-04 09:54:39 | 2024-10-04 09:54:40 |
Judging History
answer
#include<cstdio>
#define ll long long
#define maxn 1505
#define maxm 405
using namespace std;
const ll mod=1e9+7;
int n,m,q;
ll b[maxn],p[maxn][maxm],d[maxm];
struct matrix
{
int del;//偏移
ll p[maxm],val[maxm],a[maxm][maxm];
ll mul(ll x,ll y)
{
ll ret=1;
while(y)
{
if(y&1)
ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
ll inv(ll x)
{
return mul(x,mod-2);
}
void getmatrix()
{
for(int i=0;i<=m;++i)
for(int j=i;j<=m;++j)
a[i][j]=p[j-i];
}
void inv()//上三角矩阵求逆
{
int st=-1;
for(int i=0;i<=m;++i)
for(int j=m+1;j<=2*m+1;++j)
a[i][j]=0;
for(int i=0;i<=m;++i)
{
if(a[0][i])
{
st=i;
break;
}
}
if(st==-1)
return;
for(int j=st+m+1;j<=2*m+1;++j)
a[j-st-m-1][j]=1;
for(int j=m;j>=st;--j)//列1
{
int y=j+m+1;//列2
a[j-st][y]*=inv(a[j-st][j]);
for(int i=j-st-1;i>=0;--i)//行
{
a[i][y]=(a[i][y]-a[j-st][y]*a[i][j]%mod)%mod;
a[i][y]=(a[i][y]+mod)%mod;
}
}
for(int i=0;i<=m;++i)
{
for(int j=0;j<=m;++j)
{
a[i][j]=a[i][j+m+1];
a[i][j+m+1]=0;
}
}
}
void getval()
{
for(int i=0;i<=m;++i)
for(int j=0;j<=m;++j)
val[i]=(val[i]+a[i][j]*b[j]%mod)%mod;
}
}pre[maxn];
void getpre(ll a[],ll b[],ll c[])
{
for(int i=0;i<=m;++i)
c[i]=0;
for(int i=0;i<=m;++i)
for(int j=0;i+j<=m;++j)
c[i+j]=(c[i+j]+a[i]*b[j]%mod)%mod;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<=m;++i)
scanf("%lld",&b[i]);
for(int i=1;i<=n;++i)
{
for(int j=0;j<=m;++j)
{
scanf("%lld",&p[i][j]);
p[i][j]%=mod;
}
}
pre[0].p[0]=1;
pre[0].getmatrix();
pre[0].inv();
pre[0].getval();
for(int i=1;i<=n;++i)
{
pre[i].del=pre[i-1].del;
for(int j=0;j<=m;++j)
{
if(p[i][j]==0)
pre[i].del++;
else
{
for(int k=0;k<=m;++k)
d[k]=0;
for(int k=j;k<=m;++k)
d[k-j]=p[i][k];
break;
}
}
getpre(pre[i-1].p,d,pre[i].p);
pre[i].getmatrix();
pre[i].inv();
pre[i].getval();
}
for(int i=1;i<=q;++i)
{
int l,r;
scanf("%d%d",&l,&r);
ll ans=0;
int del=pre[r].del-pre[l-1].del;
for(int i=0;i+del<=m;++i)
ans=(ans+pre[r].p[i]*pre[l-1].val[i+del]%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7772kb
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: 7696kb
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: 5736kb
input:
1 1 1 604063100 57375033 742299910 257700098 1 1
output:
148903503
result:
ok 1 number(s): "148903503"
Test #4:
score: -100
Memory 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:
274042281 718260439 743573608 333451424 703686692 56883871 449220051 944476321 630364961 285404538 994196351 608379872 833786380 626934175 793580602 287004022 671717885 699219908 198738907 787601907 562908496 467667072 361977341 664730592 554160567 87901682 662015873 130469514 88456063 295610213 304...