QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#29750 | #1285. Stirling Number | alpha1022 | WA | 70ms | 25172kb | C++14 | 2.8kb | 2022-04-22 12:46:53 | 2022-04-28 15:41:48 |
Judging History
answer
#include <cstdio>
#include <algorithm>
using namespace std;
int mod, G;
typedef long long ll;
typedef __uint128_t L;
struct FastMod {
ll b, m;
FastMod(ll b): b(b), m(ll((L(1) << 64) / b)) {}
ll operator()(ll a) {
ll q = (ll)((L(m) * a) >> 64);
ll r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
} R(2);
inline int norm(int x) {
return x >= mod ? x - mod : x;
}
inline int reduce(int x) {
return x < 0 ? x + mod : x;
}
inline int mpow(int a, int b) {
int ret = 1;
for (; b; b >>= 1) {
if (b & 1)
ret = R((ll)ret * a);
a = R((ll)a * a);
}
return ret;
}
const int M = 1e6;
ll n, st, ed, k;
int r;
int GPow[M], GLog[M], inv[M];
int fac[M], ifac[M];
int a[M];
inline int getG() {
int p[20], cnt = 0;
int t = mod - 1;
for (int i = 2; i * i <= t; ++i) {
if (t % i == 0)
p[cnt++] = i;
while (t % i == 0)
t /= i;
}
if (t > 1)
p[cnt++] = t;
for (int G = 2; ; ++G) {
bool flag = 1;
for (int i = 0; i < cnt; ++i)
if (mpow(G, (mod - 1) / p[i]) == 1) {
flag = 0;
break;
}
if (flag)
return G;
}
}
int binom(ll n, ll m) {
if (n < m || m < 0)
return 0;
if (n < mod)
return R(R((ll)fac[n] * ifac[m]) * ifac[n - m]);
return R((ll)binom(n / mod, m / mod) * binom(n % mod, m % mod));
}
int calc(ll m, ll n) {
if (m < 0)
return 0;
m = min(n, m);
if (n < mod) {
int ret = R((ll)a[0] * m);
for (int k = 1, t = 0; k < mod - 1; ++k)
t = t >= m + 1 ? t - m - 1 : t - m - 1 + mod - 1,
ret = R(R((ll)(GPow[t] - 1) * inv[GPow[mod - 1 - k] - 1]) * a[k] + ret);
ret = reduce(-ret);
return ret;
}
m -= k;
if (m < 0)
return 0;
ll a = m / (mod - 1);
int b = m % (mod - 1);
int tmp = binom(k - 1, a);
if ((k - a - 1) & 1)
tmp = reduce(-tmp);
int ret = R((ll)tmp * (calc(b - mod + 1, r) - calc(b, r) + mod));
if (b < r && a > 0) {
tmp = binom(k - 1, a - 1);
if ((k - a) & 1)
tmp = reduce(-tmp);
ret = R((ll)tmp * (calc(b, r) - calc(b + mod - 1, r) + mod) + ret);
}
return ret;
}
int main() {
scanf("%lld%lld%lld%d", &n, &st, &ed, &mod);
R = FastMod(mod), G = getG();
GPow[0] = 1;
for (int i = 1; i < mod - 1; ++i)
GLog[GPow[i] = R((ll)GPow[i - 1] * G)] = i;
inv[1] = 1;
for (int i = 2; i < mod - 1; ++i)
inv[i] = GPow[mod - 1 - GLog[i]];
fac[0] = ifac[0] = 1;
for (int i = 1; i <= mod - 1; ++i)
fac[i] = R((ll)fac[i - 1] * i),
ifac[i] = R((ll)ifac[i - 1] * inv[i]);
k = n / mod, r = n % mod;
for (int k = 0; k < mod - 1; ++k) {
int x = GPow[k];
if (x < mod - r + 1)
a[k] = R((ll)fac[x + r - 1] * ifac[x - 1]);
}
printf("%d\n", reduce(calc(ed, n) - calc(st - 1, n)));
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 10028kb
input:
4 1 4 5
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9920kb
input:
6 5 5 29
output:
15
result:
ok "15"
Test #3:
score: 0
Accepted
time: 70ms
memory: 25172kb
input:
1000 685 975 999983
output:
482808
result:
ok "482808"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 9960kb
input:
8 7 8 7
output:
2
result:
wrong answer 1st words differ - expected: '1', found: '2'