NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	1ms	320 KiB
#2	Accepted 5	1ms	420 KiB
#3	Accepted 5	1ms	404 KiB
#4	Accepted 5	1ms	316 KiB
#5	Accepted 5	1ms	404 KiB
#6	Accepted 5	1ms	412 KiB
#7	Accepted 5	1ms	324 KiB
#8	Accepted 5	1ms	404 KiB
#9	Accepted 5	1ms	404 KiB
#10	Accepted 5	1ms	404 KiB
#11	Accepted 5	4ms	536 KiB
#12	Accepted 5	40ms	2.7 MiB
#13	Accepted 5	1ms	404 KiB
#14	Accepted 5	3ms	496 KiB
#15	Accepted 5	36ms	2.4 MiB
#16	Accepted 5	15ms	1.1 MiB
#17	Accepted 5	2ms	404 KiB
#18	Accepted 5	3ms	532 KiB
#19	Accepted 5	40ms	2.5 MiB
#20	Accepted 5	20ms	1.4 MiB

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define ull unsigned long long
#define db double
using namespace std;
const int MAXN = 1e6 + 5, mod = 1e9 + 7;

int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0')
		f = ch == '-' ? -f : f, ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return x * f;
}

struct node {
	int c, d;
	friend bool operator < (const node A, const node B) {
		return A.c < B.c;
	}
} a[MAXN];

int Quick_pow(int a, int b) {
	if (a == 0) return 1ll;
//	if (b == 0) return 1ll;
	int res = 1;
	while (b){
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int Inv(int i) {
	return Quick_pow(i, mod - 2);
}

int n, m, v;
int f[MAXN];

signed main() {
//	if (!system("fc assign.out assign3.ans")) puts("Yes");
//	else puts("No");
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int T;
	T = read();
	while (T --){
		n = read(), m = read(), v = read();
		int fl = 1;
		for (int i = 1; i <= m; i ++) a[i].c = read(), a[i].d = read();
//		if (T == 6){
//			puts("");
//			printf("%lld %lld %lld\n", n, m, v);
//			for (int i = 1; i <= m; i ++) printf("%lld %lld\n", a[i].c, a[i].d);
//			puts("");
//		}
		sort(a + 1, a + m + 1);
		if (a[1].c == 1) f[1] = 1ll;
		else f[1] = Quick_pow(v * v % mod, a[1].c - 1);
		for (int i = 2; i <= m; i ++){
			if (a[i - 1].c == a[i].c){
				if (a[i - 1].d == a[i].d){
					f[i] = f[i - 1];
					continue;
				}
				else {
					fl = 0;
					break;
				}
			}
			if (a[i - 1].c == a[i].c - 1)
				f[i] = f[i - 1] * ((v * v % mod - ((v - 1 + mod) % mod) + mod) % mod) % mod;
			else {
				int del = a[i].c - a[i - 1].c;
				f[i] = f[i - 1] * ((Quick_pow(v * v % mod, del) - (Quick_pow(v % mod, del - 1) * (v - 1) % mod) + mod) % mod) % mod;
			}
		}
		if (fl == 0){
			puts("0");
			continue;
		}
		printf("%lld\n", f[m] * Quick_pow(v * v % mod, n - a[m].c) % mod);
	}
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

*/

递交者: CQ-0092
题目: NOIP2024BGF NOIP2024BGF
比赛: 【官方数据 CQ】 NOIP2024 批量测试
语言: C++14(O2)
代码长度: 2.2 KiB
递交时间: 2024-12-6 16:36:55
评测时间: 2024-12-6 16:43:50

分数: 100
总耗时: 175ms
峰值时间: 40ms
峰值内存: 2.7 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录