QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608976#8717. 骰子UESTC_OldEastWestWA 1044ms17204kbC++172.3kb2024-10-04 09:57:512024-10-04 09:57:51

Judging History

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

  • [2024-10-04 09:57:51]
  • 评测
  • 测评结果:WA
  • 用时:1044ms
  • 内存:17204kb
  • [2024-10-04 09:57:51]
  • 提交

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];
ll A[maxm][maxm];
struct matrix
{
	int del;//偏移
	ll p[maxm],val[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: 0ms
memory: 5756kb

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

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

input:

1 1 1
604063100 57375033
742299910 257700098
1 1

output:

148903503

result:

ok 1 number(s): "148903503"

Test #4:

score: -100
Wrong Answer
time: 1044ms
memory: 17204kb

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...

result:

wrong answer 1st numbers differ - expected: '66394849', found: '274042281'