警示后人

GeorgeAAAADHD @ 2024-11-30 20:42:35

by GeorgeAAAADHD @ 2024-11-30 20:43:17

如果不使用快读但关同步流的话也有可能被卡

by Night_sea_64 @ 2024-11-30 20:45:49

我觉得不会。我自己写了个纯 cin 的稳过，而且 CCF 神机不至于

by GeorgeAAAADHD @ 2024-11-30 20:49:50

@Night_sea_64 反正我挂了一发，改快读过了

希望不要挂分

by dthythxth_Huge_Brain @ 2024-11-30 20:53:46

@GeorgeAAAADHD 为何我开了快读，关了long long 还是80 /ll

by GeorgeAAAADHD @ 2024-11-30 20:54:51

@dthythxth_Huge_Brain 那可能是算法复杂度有误或者你真的写丑了

by dthythxth_Huge_Brain @ 2024-11-30 20:56:10

@GeorgeAAAADHD

#include <bits/stdc++.h>
namespace FAST_IO {
const int LEN = 1 << 18;
char BUF[LEN], PUF[LEN], space = ' ', line = '\n';
int Pin = LEN, Pout;
inline void flushin() {
    memcpy(BUF, BUF + Pin, LEN - Pin), fread(BUF + LEN - Pin, 1, Pin, stdin),
        Pin = 0;
    return;
}
inline void flushout() {
    fwrite(PUF, 1, Pout, stdout), Pout = 0;
    return;
}
inline char Getc() {
    return (Pin == LEN ? (fread(BUF, 1, LEN, stdin), Pin = 0) : 0), BUF[Pin++];
}
inline char Get() { return BUF[Pin++]; }
inline void Putc(char x) {
    if (Pout == LEN)
        flushout(), Pout = 0;
    PUF[Pout++] = x;
}
inline void Put(char x) { PUF[Pout++] = x; }
template <typename tp = int> inline void read(int &X) {
    (Pin + 32 >= LEN) ? flushin() : void();
    tp res = 0;
    char f = 1, ch = ' ';
    for (; ch < '0' || ch > '9'; ch = Get())
        if (ch == '-')
            f = -1;
    for (; ch >= '0' && ch <= '9'; ch = Get())
        res = (res << 3) + (res << 1) + ch - 48;
    X = res * f;
    return;
}
template <typename tp = char> inline void read(char &X) {
    X = Getc();
    return;
}
template <typename tp> inline void wt(tp a) {
    if (a > 9)
        wt(a / 10);
    Put(a % 10 + '0');
    return;
}
template <typename tp = int> inline void write(int a) {
    static int stk[20], top;
    (Pout + 32 >= LEN) ? flushout() : void();
    if (a < 0)
        Put('-'), a = -a;
    else if (a == 0)
        Put('0');
    for (top = 0; a; a /= 10)
        stk[++top] = a % 10;
    for (; top; --top)
        Put(stk[top] ^ 48);
    return;
}
template <typename tp = char> inline void write(char a) {
    Put(a);
    return;
}
template <typename T, typename... Args> void read(T &tmp, Args &...tmps) {
    read(tmp), read(tmps...);
}
template <typename T, typename... Args> void write(T &tmp, Args &...tmps) {
    write(tmp), write(tmps...);
}
} // namespace FAST_IO
using namespace FAST_IO;
const int mod = 1e9 + 7;
int t, n, m, v, ans, lst;
struct st {
    int c, d;
} a[100002];
int qpow(int x, int y, int mod) {
    if (y < 1)
        return 1;
    int tmp = qpow(x, y / 2, mod);
    if (y & 1)
        return 1ll * x * tmp % mod * tmp % mod;
    return 1ll * tmp * tmp % mod;
}
inline int inv(int x) { return qpow(x, mod - 2, mod); }
inline int S(int x, int n) {
    return 1ll * (qpow(x, n + 1, mod) - 1) % mod * inv(x - 1) % mod;
}
void solve(int l, int r) {
    int val = S(v, 2 * (r - l) - 1) - S(v, 2 * (r - l) - r + l - 1);
    val = (val + mod) % mod;
    val = 1ll * val * (v - 1) % mod;
    val = (val + qpow(v, 2 * (r - l) - r + l, mod)) % mod;
    ans = 1ll * ans * val % mod;
}
void sol(int l, int r) {
    int val = S(v, 2 * (r - l) - 1) - S(v, 2 * (r - l) - r + l - 1);
    val = (val + mod) % mod;
    val = 1ll * val * (v - 1) % mod;
    val = (val + qpow(v, 2 * (r - l) - r + l - 1, mod)) % mod;
    ans = 1ll * ans * val % mod;
}
signed main() {
    read(t);
    for (; t--;) {
        read(n, m, v), ans = lst = 1;
        for (int i = 1; i <= m; i++)
            read(a[i].c, a[i].d);
        std::sort(a + 1, a + 1 + m, [](st x, st y) { return x.c < y.c; });
        for (int i = 1; i <= m; i++)
            if (a[i].c == a[i - 1].c && a[i].d != a[i - 1].d)
                ans = 0;
        if (!ans) {
            puts("0");
            continue;
        }
        for (int i = 1; i <= m; i++) {
            if (a[i].c == a[i - 1].c)
                continue;
            if (lst == 1 && i == 1 && a[i].c != 1)
                solve(lst, a[i].c);
            else if (a[i].c != 1)
                sol(lst, a[i].c);
            lst = a[i].c;
        }
        if (a[m].c != n)
            solve(a[m].c, n);
        printf("%d\n", ans);
    }
    return 0;
}
/*
    1 0 0 0 1
(v-1)*v*v*v*v*v*v*v
(v-1)*v*v*v*v*v*v*v
(v-1)*v*v*v*v*v*v*v
(v-1)*v*v*v*v*v*v*v
*/

我感觉就是 mlogn的啊

by GeorgeAAAADHD @ 2024-11-30 21:04:03

@dthythxth_Huge_Brain

我看不出来，建议是减少取模次数

看了一下你调用快速幂函数的次数是比我多的，实际上不需要那么复杂

by dthythxth_Huge_Brain @ 2024-11-30 21:05:01

@GeorgeAAAADHD 已经过了，死因：没有预处理逆元

by GeorgeAAAADHD @ 2024-11-30 21:07:37

@dthythxth_Huge_Brain

那也确实是一个比较唐诗的错误了，我之前也因为这个似过

祝您不挂分