这题数据量挺大,正好可以当做一个性能测试横向对比的好题。
考虑到每个测试点输入的整数上限是 $9\times 10^6$ 个, 为了避免巨量输入输出对本题带来的影响,我们考虑使用快读快写 + getchar_unlocked
/putchar_unlocked
优化。
一般取模
我们知道,一般情况下取模运算直接用 %
就可以了,所以我们很显然可以写出以下代码:
#include <stdio.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
int rd()
{
int k = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9')
{
if (s == '-')
f = 0;
s = getchar();
}
while (s >= '0' && s <= '9')
{
k = (k << 1) + (k << 3) + (s ^ '0');
s = getchar();
}
return f ? k : -k;
}
void wr(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar((x % 10) ^ '0');
}
int trim(int x, int mod) { return (x >= 0) ? (x % mod) : (mod - (((-x) % mod) ? ((-x) % mod) : mod)); }
int add(int a, int b, int mod) { return (a + b >= mod) ? (a + b - mod) : (a + b); }
int mul(int a, int b, int mod) { return 1ll * a * b % mod; }
int quick_pow(int x, int p, int mod)
{
x = trim(x, mod);
int ans = 1;
while (p)
{
if (p & 1)
ans = mul(ans, x, mod);
x = mul(x, x, mod);
p >>= 1;
}
return trim(ans, mod);
}
int main()
{
int T = rd();
while (T--)
{
int M = rd(), H = rd(), A = 0, B = 0, ans = 0;
while (H--)
A = rd(), B = rd(), ans = add(ans, quick_pow(A, B, M), M);
wr(ans), putchar('\n');
}
}
这个代码避免了各种STL和大常数的时候不开O2跑的特别慢的情况,按理来说在不开O2优化的情况下应该很快了,但是实际上跑不过第三个点。开了火车头才能过,此时3个点的总用时是 2.3s 。说白了,取模运算还是太慢了,我们可以使用另外一种 Barrett
模乘算法,将所有的取模和除法运算全部用加减乘来解决。
Barrett 模乘优化
具体代码可以见 AcWing 1651. 锻炼 的题面以及其原理介绍。这里给出的 Barrett 模乘源码对于 $M\ge 2$ 时都是适用的(分析源码原理不难得出,$M=1$ 时会出现溢出情况从而无法正常使用)。那么对于 $M=1$ 的情况,我们直接特判就行了。甚至快速输出里面针对进制 $10$ 的除法和取模我们也可以使用 Barrett
优化完成,但是实际测下来三组总时间反而比不优化快写的除法取模反而要慢了大概 10ms ,所以快写这里还是不做优化了,就在正常的取模运算当中做优化就行了。在不开 O2 优化的情况下三组数据轻松跑完,加了火车头之后三组数据总时间更是达到了 839ms 。妈妈再也不用担心我被取模卡时间啦!
以下代码是模数 unsigned long long
范围下使用的 Barrett
。如果保证模数范围在 $1\le p\le 2^{30}-1$ 的话(比如本题),那直接用下面这个就行,这样还可以进一步优化细微的时间常数。
struct Barrett
{
u32 m, b;
Barrett(const u32& _m = 2) : m(_m), b((u32)(-1) / m + 1) {}
friend inline u32 operator% (const u32& a, const Barrett& mod)
{
u32 r = a - mod.m * ((u64)(a) * mod.b >> 32);
return mod.m == 1 ? 0 : r >= mod.m ? r + mod.m : r;
}
};
#include <stdio.h>
typedef unsigned long long u64;
typedef __uint128_t u128;
#define getchar getchar_unlocked
#define putchar putchar_unlocked
int rd()
{
int k = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9')
{
if (s == '-')
f = 0;
s = getchar();
}
while (s >= '0' && s <= '9')
{
k = (k << 1) + (k << 3) + (s ^ '0');
s = getchar();
}
return f ? k : -k;
}
void wr(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar((x % 10) ^ '0');
}
struct Barrett
{
u64 m, b;
Barrett(const u64& _m = 2) : m(_m), b((u64)(-1) / m + 1) {}
friend inline u64 operator% (const u64& a, const Barrett& mod)
{
u64 r = a - mod.m * ((u128)(a) * mod.b >> 64);
return mod.m == 1 ? 0 : r >= mod.m ? r + mod.m : r;
}
};
Barrett mod;
int quick_pow(int x, int p, const Barrett& mod)
{
x = x % mod;
int ans = 1;
while (p)
{
if (p & 1)
ans = (1ll * ans * x) % mod;
x = (1ll * x * x) % mod;
p >>= 1;
}
return ans;
}
int main()
{
int T = rd();
while (T--)
{
int M = rd(), H = rd(), A = 0, B = 0, ans = 0;
mod = Barrett(M);
while (H--)
A = rd(), B = rd(), ans = (ans + quick_pow(A, B, mod)) % mod;
wr(ans), putchar('\n');
}
}
刚刚看还只有
一个人