NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	1ms	324 KiB
#2	Accepted 5	1ms	404 KiB
#3	Accepted 5	1ms	316 KiB
#4	Accepted 5	1ms	404 KiB
#5	Accepted 5	1ms	408 KiB
#6	Accepted 5	1ms	404 KiB
#7	Accepted 5	1ms	404 KiB
#8	Accepted 5	1ms	404 KiB
#9	Accepted 5	1ms	408 KiB
#10	Accepted 5	1ms	404 KiB
#11	Accepted 5	4ms	404 KiB
#12	Accepted 5	41ms	1.5 MiB
#13	Accepted 5	1ms	404 KiB
#14	Accepted 5	3ms	404 KiB
#15	Accepted 5	36ms	1.4 MiB
#16	Accepted 5	14ms	788 KiB
#17	Accepted 5	1ms	512 KiB
#18	Accepted 5	3ms	404 KiB
#19	Accepted 5	39ms	1.5 MiB
#20	Accepted 5	19ms	916 KiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;

template < typename T >
inline void read(T &x)
{
    x = 0;
    bool flg = 0;
    char c;
    while ((c = getchar()) < 48 || c > 57)
        if (c == '-') flg = 1;
    do
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
    } while ((c = getchar()) > 47 && c < 58);
    if (flg) x = -x;
}

int OUTPUT[45];

template < typename T >
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    int len = 0;
    do
    {
        OUTPUT[++len] = (x % 10) | 48;
        x /= 10;
    } while (x);
    while (len)
        putchar(OUTPUT[len--]);
}

template < typename T >
inline void writesp(T x)
{
    write(x);
    putchar(32);
}

template < typename T >
inline void writeln(T x)
{
    write(x);
    putchar(10);
}

const int N = 1e5 + 5, P = 1e9 + 7;
pair < int, int > a[N];
int b[N];

inline int power(int x, int y)
{
    int ret = 1;
    while (y)
    {
        if (y & 1) ret = (ll)ret * x % P;
        x = (ll)x * x % P;
        y >>= 1;
    }
    return ret;
}

int main()
{
    freopen("assign.in", "r", stdin);
    freopen("assign.out", "w", stdout);
    int T;
    read(T);
    while (T--)
    {
        int n, m, v, len = 0, ans = 1;
        read(n);
        read(m);
        read(v);
        for (int i = 1; i <= m; ++i)
        {
            read(a[i].first);
            read(a[i].second);
        }
        sort(a + 1, a + m + 1);
        for (int i = 1; i < m; ++i)
            if (a[i].first == a[i + 1].first && a[i].second != a[i + 1].second)
            {
                puts("0");
                goto End;
            }
        for (int i = 1; i <= m; ++i)
        {
            int p = i;
            while (p < m && a[p + 1].first == a[p].first)
                ++p;
            b[++len] = a[i].first;
            i = p;
        }
        if (!len) ans = power((ll)v * v % P, n - 1);
        else
        {
            if (b[1] > 1) ans = (ll)ans * power((ll)v * v % P, b[1] - 1) % P;
            for (int i = 1; i < len; ++i)
                ans = (ll)ans * (power((ll)v * v % P, b[i + 1] - b[i]) - (ll)power(v, b[i + 1] - b[i] - 1) * (v - 1ll) % P + P) % P;
            if (b[len] < n) ans = (ll)ans * power((ll)v * v % P, n - b[len]) % P;
        }
        writeln(ans);
        End:;
    }
    return 0;
}

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

分数: 100
总耗时: 173ms
峰值时间: 41ms
峰值内存: 1.5 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录