NOI批量评测 - 记录详情

foo.cc: In function 'int main()':
foo.cc:134:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  134 |         scanf("%d",&T);
      |                ~^  ~~
      |                 |  |
      |                 |  long long int*
      |                 int*
      |                %lld
Expand

#	状态分数	耗时	内存占用

#1	Wrong Answer 0 读取到 16，应为 14。	2ms	404 KiB
#2	Wrong Answer 0 读取到 972，应为 784。	2ms	404 KiB
#3	Wrong Answer 0 读取到 178，应为 126。	1ms	320 KiB
#4	Wrong Answer 0 读取到 65517，应为 27648。	1ms	404 KiB
#5	Accepted 5	1ms	404 KiB
#6	Accepted 5	1ms	316 KiB
#7	Accepted 5	1ms	404 KiB
#8	Accepted 5	1ms	404 KiB
#9	Accepted 5	1ms	408 KiB
#10	Wrong Answer 0 读取到 416705681，应为 903189684。	2ms	408 KiB
#11	Wrong Answer 0 读取到 866159417，应为 5568271。	7ms	832 KiB
#12	Wrong Answer 0 读取到 530448951，应为 789710747。	64ms	4.3 MiB
#13	Wrong Answer 0 读取到 437428882，应为 557107545。	2ms	404 KiB
#14	Wrong Answer 0 读取到 958032884，应为 416764931。	15ms	788 KiB
#15	Wrong Answer 0 读取到 347716634，应为 974223963。	201ms	4.2 MiB
#16	Wrong Answer 0 读取到 7096448，应为 430640767。	195ms	4.2 MiB
#17	Wrong Answer 0 读取到 901240880，应为 917840098。	3ms	404 KiB
#18	Wrong Answer 0 读取到 305963078，应为 741021006。	15ms	788 KiB
#19	Wrong Answer 0 读取到 528529783，应为 998606827。	201ms	4.2 MiB
#20	Wrong Answer 0 读取到 227946647，应为 177682655。	213ms	4.3 MiB

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define int long long
const int N=1e7+10,Mod=1e9+7;

void read(int &x)
{
	int w=1,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-w;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		f*=10;f+=ch-'0';
		ch=getchar();
	}
	x=w*f;
}
//void read(LL &x)
//{
//	LL w=1,f=0;
//	char ch=getchar();
//	while(ch<'0'||ch>'9')
//	{
//		if(ch=='-') w=-w;
//		ch=getchar();
//	}
//	while(ch>='0'&&ch<='9')
//	{
//		f*=10;f+=ch-'0';
//		ch=getchar();
//	}
//	x=w*f;
//}

int n,m,v;
struct A{
	int c,d;
	bool operator < (const A &a) const{return c<a.c;}
}a[N];
LL f[N];//0 no 1 yes
bool flag=0;

LL ksm(LL a,LL b,LL Mod)
{
//	printf("ksm will %lld %lld %lld\n",a,b,Mod);
	LL ans=1;
	while(b)
	{
		if(b&1) ans*=a,ans%=Mod;
		a*=a;
		a%=Mod;
//		if(flag) 
//			printf("ksm:%lld %lld %lld %lld\n",a,a*a%Mod,b,ans);
		b>>=1;
	}
//	printf("ksm=%lld\n",ans);
	return ans;
}

LL del[N],tr[N];

void solve()
{
	read(n);read(m);read(v);
	for(int i=1;i<=m;i++) read(a[i].c),read(a[i].d);
	sort(a+1,a+1+m);
	for(int i=1;i<=m;i++)
	{
		if(a[i].c==a[i-1].c&&a[i].d!=a[i-1].d)
		{
			puts("0");
			return ;
		}
	}
	LL vv=v*v%Mod;
	flag=1;
//	ksm(464289274*464289274%Mod,557584238-1,Mod);
	for(int i=2;i<=m;i++)
	{
		if(a[i].c!=a[i-1].c)
		{
			flag=0;
			break;
		}
	}
	LL all=ksm(v*v%Mod,n-1,Mod);
	if(flag)
	{
		printf("%lld\n",all);
		return ;
	}
	for(int i=2;i<=m;i++)
	{
		if(a[i].c==a[i-1].c) continue;
		LL jump=a[i].c-a[i-1].c-1;
		LL x=0;
		if(jump==0)
		{
			x=v-1;
		}
		else
		{
			x=ksm(v,jump,Mod)*(v-1)%Mod;
		}
//		printf("%d:%lld\n",i,del);
		del[i-1]=x;
		tr[i-1]=ksm(vv,jump+1,Mod)-del[i-1];
		tr[i-1]=(tr[i-1]%Mod+Mod)%Mod;
	}
//	printf("%lld %lld\n",all,del);
	f[1]=del[1];
	LL inv=tr[1];
	for(int i=2;i<m;i++)
	{
		f[i]=tr[i]*f[i-1]+del[i]*(inv-f[i-1]);
		inv*=tr[i];
		inv%=Mod;
	}
	LL ans=((all-f[m-1])%Mod+Mod)%Mod;
//	printf("qwq ");
	printf("%lld\n",ans);
}

signed main()
{
	freopen("assign.in","r",stdin);//�Ļ��� 
	freopen("assign.out","w",stdout);
	int T=1;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

递交者: TJ-0112
题目: NOIP2024B NOIP2024B
比赛: 【民间数据】NOIP2024 TJ 批量测试
语言: C++14(O2)
代码长度: 2.2 KiB
递交时间: 2024-12-1 0:49:51
评测时间: 2024-12-1 0:55:26

分数: 25
总耗时: 930ms
峰值时间: 213ms
峰值内存: 4.3 MiB

25 Wrong Answer

代码

信息

25 Wrong Answer

代码

信息

还没有账户？

登录