NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	1ms	392 KiB
#2	Accepted 5	1ms	400 KiB
#3	Accepted 5	1ms	336 KiB
#4	Accepted 5	1ms	404 KiB
#5	Accepted 5	1ms	320 KiB
#6	Accepted 5	1ms	508 KiB
#7	Accepted 5	1ms	404 KiB
#8	Accepted 5	1ms	404 KiB
#9	Accepted 5	1ms	404 KiB
#10	Accepted 5	1ms	320 KiB
#11	Accepted 5	3ms	532 KiB
#12	Accepted 5	28ms	1.8 MiB
#13	Accepted 5	2ms	404 KiB
#14	Accepted 5	3ms	404 KiB
#15	Accepted 5	37ms	1.8 MiB
#16	Accepted 5	15ms	916 KiB
#17	Accepted 5	2ms	408 KiB
#18	Accepted 5	4ms	448 KiB
#19	Accepted 5	40ms	1.9 MiB
#20	Accepted 5	19ms	1 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}
	return x*w; 
}
const int mod=1e9+7,MAXN=1e5+10;
int n,m;
ll v;
int c[MAXN],d[MAXN];
ll ksm(ll a,int b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll ans=0;
int a[30],aa[30];
pair<int,int>ck[30];
void solve(int x){
	if(x==n){
		int okm=0;
		for(int i=1;i<n;i++){
			if(a[i]){
				if(ck[i].first==a[i]){
					if(a[i+1]!=0&&a[i+1]!=ck[i].second){
						okm=1;break; 
					}
					else a[i+1]=ck[i].second;
				}
			}
//			cout<<t[i].first<<" "<<t[i].second<<endl;;
		}
//		cout<<okm<<endl;
		if(okm)ans++;
//		if(okm){
//			for(int i=1;i<n;i++)cout<<ck[i].first<<" "<<ck[i].second<<endl;cout<<endl;
//		}
		for(int i=1;i<=n;i++)a[i]=aa[i];
		return ;
	}else{
		for(int i=1;i<=v;i++)for(int j=1;j<=v;j++){
			ck[x]=make_pair(i,j);
			solve(x+1);
		}
	}
}
void bl(){
	for(int i=1;i<=n;i++)a[i]=0;
	for(int i=1;i<=m;i++){
		if(a[c[i]]!=0&&a[c[i]]!=d[i]){
			printf("0\n");return ;
		}else a[c[i]]=d[i];
	}
	for(int i=1;i<=n;i++)aa[i]=a[i];
	solve(1);
	printf("%lld\n",ksm(v*1ll*v%mod,n-1)-ans);
} 
pair<int,int> t[MAXN];
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T=read();
	while(T--){
//		init();
		ans=0;
		n=read();m=read();v=read();
		int flag=0;
		for(int i=1;i<=m;i++){
			c[i]=read();d[i]=read();
			if(c[i]!=i)flag=1;
			t[i]=make_pair(c[i],d[i]);
		}
//		if(n<=12){
//			bl();
//		}else
		if(m==1){
			printf("%lld\n",ksm(v*1ll*v%mod,n-1));
			continue;
		}
		else if(n==m&&!flag){
			printf("%lld\n",ksm((v*1ll*v-(v-1))%mod,n-1));
			continue; 
		}
//		else
//		if(!flag2){
			sort(t+1,t+m+1);
			int okm=1;
			for(int i=2;i<=m;i++){
				if(t[i].first==t[i-1].first&&t[i].second!=t[i-1].second){
					printf("0\n");okm=0;
					break;
				}
			}
			if(okm==0)continue;
			ll res=1;
			for(int i=2;i<=m;i++){
				if(t[i].first==t[i-1].first)continue;
				ll T=(ksm(v*1ll*v%mod,t[i].first-t[i-1].first)%mod-ksm(v%mod,t[i].first-t[i-1].first-1)%mod*(v-1)%mod);
				T=(T%mod+mod);
				res=T*res%mod;
			}
//			cout<<n<<" "<<m<<" "<<ksm(v*1ll*v%mod,n-1)<<" "<<t[1].first-1<<" "<<n-t[m].first<<" "<<ksm(v*v%mod,t[1].first-1+n-t[1].first)<<" "<<ksm(v*v,t[1].first-1)*ksm(v*v,n-t[1].first)%mod<<endl;
			res=res*ksm(v*1ll*v%mod,t[1].first-1)%mod*ksm(v*1ll*v%mod,n-t[m].first)%mod;
			res=(res+mod)%mod;
			printf("%lld\n",res%mod);
//		}
	}
	
	return 0;
}
/*
//��ұ�ұ�� 
1
1000000 1 114514
100 1
*/

递交者: SH-0020
题目: NOIP2024BGF NOIP2024BGF
比赛: 【官方数据 SH】 NOIP2024 批量测试
语言: C++14(O2)
代码长度: 2.7 KiB
递交时间: 2024-12-6 17:23:42
评测时间: 2024-12-6 17:23:44

分数: 100
总耗时: 166ms
峰值时间: 40ms
峰值内存: 1.9 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录