QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#889489 | #1084. Beautiful Sequence Unraveling | caijianhong | AC ✓ | 329ms | 5760kb | C++17 | 3.5kb | 2025-02-08 16:15:34 | 2025-02-08 16:16:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <int id>
struct modint {/*{{{*/
static int mod;
static unsigned umod;
static void setmod(int p) { mod = umod = p; }
unsigned v;
modint() : v(0) {}
template <class T, must_int<T> = 0>
modint(T x) {
x %= mod;
v = x < 0 ? x + mod : x;
}
modint operator+() const { return *this; }
modint operator-() const { return modint() - *this; }
friend int raw(const modint &self) { return self.v; }
friend ostream& operator<<(ostream& os, const modint &self) {
return os << raw(self);
}
modint &operator+=(const modint &rhs) {
v += rhs.v;
if (v >= umod) v -= umod;
return *this;
}
modint &operator-=(const modint &rhs) {
v -= rhs.v;
if (v >= umod) v += umod;
return *this;
}
modint &operator*=(const modint &rhs) {
v = 1ull * v * rhs.v % umod;
return *this;
}
modint &operator/=(const modint &rhs) {
assert(rhs.v);
return *this *= qpow(rhs, mod - 2);
}
template <class T, must_int<T> = 0>
friend modint qpow(modint a, T b) {
modint r = 1;
for (; b; b >>= 1, a *= a)
if (b & 1) r *= a;
return r;
}
friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
bool operator==(const modint &rhs) const { return v == rhs.v; }
bool operator!=(const modint &rhs) const { return v != rhs.v; }
};/*}}}*/
template <int id>
unsigned modint<id>::umod;
template <int id>
int modint<id>::mod;
using mint = modint<-1>;
int n, m;
mint f[410][410], pw[410][410], binom[410][410], a[410], inv[410];
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m >> mint::mod;
mint::setmod(mint::mod);
for (int i = 0; i <= n; i++) {
pw[i][0] = binom[i][0] = 1;
for (int j = 1; j <= n; j++) pw[i][j] = pw[i][j - 1] * i;
for (int j = 1; j <= i; j++) binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
}
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = -mint::mod / i * inv[mint::mod % i];
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= n; i++) {
f[i][j] = pw[j][i];
}
}
for (int j = 1; j <= n; j++) {
// mint now1 = 0, now2 = 0;
mint now1[410] = {}, now2[410] = {};
for (int i = 1; i <= n; i++) {
for (int t = 1; t <= j; t++) f[i][j] -= now1[t] - now2[t];
for (int t = 1; t <= j; t++) {
now1[t] = (now1[t] + f[i][j - t + 1] - f[i][j - t]) * t;
now2[t] = (now2[t] + f[i][j - t + 1] - f[i][j - t]) * (t - 1);
}
// for (int k = 1; k < i; k++) {
// f[i][j] -= (pw[t][k] - pw[t - 1][k]) * (f[i - k][j - t + 1] - f[i - k][j - t]);
// }
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) a[i] += binom[i][j] * ((i - j) & 1 ? -1 : +1) * f[n][j];
}
mint ans = 0;
mint now = 1;
for (int i = 1; i <= n; i++) {
now *= m - i + 1;
now *= inv[i];
ans += now * a[i];
}
cout << ans << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5760kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5632kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 61ms
memory: 5760kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 0ms
memory: 5632kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5504kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5760kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5632kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 328ms
memory: 5760kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 327ms
memory: 5760kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 5760kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 0ms
memory: 5632kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 5760kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5632kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 327ms
memory: 5760kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 327ms
memory: 5632kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 326ms
memory: 5760kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 329ms
memory: 5632kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 325ms
memory: 5760kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 323ms
memory: 5632kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 320ms
memory: 5632kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"