QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #800238 | #9656. Edge, Path, Number | ucup-team004 | AC ✓ | 35ms | 9992kb | C++23 | 8.5kb | 2024-12-06 02:10:36 | 2024-12-06 02:10:36 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
template<class T>
constexpr T power(T a, u64 b, T res = 1) {
for (; b != 0; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
return u64(a) * b % P;
}
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
res %= P;
return res;
}
constexpr i64 safeMod(i64 x, i64 m) {
x %= m;
if (x < 0) {
x += m;
}
return x;
}
constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
a = safeMod(a, b);
if (a == 0) {
return {b, 0};
}
i64 s = b, t = a;
i64 m0 = 0, m1 = 1;
while (t) {
i64 u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) {
m0 += b / s;
}
return {s, m0};
}
template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
constexpr ModIntBase() : x(0) {}
template<std::unsigned_integral T>
constexpr ModIntBase(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr ModIntBase(T x_) {
using S = std::make_signed_t<U>;
S v = x_ % S(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static U mod() {
return P;
}
constexpr U val() const {
return x;
}
constexpr ModIntBase operator-() const {
ModIntBase res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr ModIntBase inv() const {
return power(*this, mod() - 2);
}
constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
x = mulMod<mod()>(x, rhs.val());
return *this;
}
constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
return *this *= rhs.inv();
}
friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
return os << a.val();
}
friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() <=> rhs.val();
}
private:
U x;
};
template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;
struct Barrett {
public:
Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}
constexpr u32 mod() const {
return m;
}
constexpr u32 mul(u32 a, u32 b) const {
u64 z = a;
z *= b;
u64 x = u64((u128(z) * im) >> 64);
u32 v = u32(z - x * m);
if (m <= v) {
v += m;
}
return v;
}
private:
u32 m;
u64 im;
};
template<u32 Id>
struct DynModInt {
public:
constexpr DynModInt() : x(0) {}
template<std::unsigned_integral T>
constexpr DynModInt(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr DynModInt(T x_) {
int v = x_ % int(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static void setMod(u32 m) {
bt = m;
}
static u32 mod() {
return bt.mod();
}
constexpr u32 val() const {
return x;
}
constexpr DynModInt operator-() const {
DynModInt res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr DynModInt inv() const {
auto v = invGcd(x, mod());
assert(v.first == 1);
return v.second;
}
constexpr DynModInt &operator*=(const DynModInt &rhs) & {
x = bt.mul(x, rhs.val());
return *this;
}
constexpr DynModInt &operator+=(const DynModInt &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr DynModInt &operator-=(const DynModInt &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr DynModInt &operator/=(const DynModInt &rhs) & {
return *this *= rhs.inv();
}
friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
return os << a.val();
}
friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() <=> rhs.val();
}
private:
u32 x;
static Barrett bt;
};
template<u32 Id>
Barrett DynModInt<Id>::bt = 998244353;
using Z = ModInt<1000000007>;
void solve() {
int N, M, K, P, X;
std::cin >> N >> M >> K >> P >> X;
std::vector<int> pw(K + 1);
pw[0] = 1;
for (int i = 1; i <= K; i++) {
pw[i] = pw[i - 1] * 10;
}
std::vector<std::array<int, 3>> edges(M);
for (int i = 0; i < M; i++) {
int u, v, w;
std::cin >> u >> v >> w;
u--;
v--;
edges[i] = {u, v, w};
}
int h = K / 2;
std::vector dp1(N, std::vector<Z>(1, 1)), dp2(N, std::vector<Z>(1, 1));
for (int i = 0; i < h; i++) {
std::vector ndp(N, std::vector<Z>(std::min(pw[i + 1], P)));
for (auto [u, v, w] : edges) {
for (int x = 0; x < std::min(pw[i], P); x++) {
ndp[v][(x * 10 + w) % P] += dp1[u][x];
}
}
dp1 = std::move(ndp);
}
for (int i = 0; i < K - h; i++) {
std::vector ndp(N, std::vector<Z>(std::min(pw[i + 1], P)));
for (auto [u, v, w] : edges) {
for (int x = 0; x < std::min(pw[i], P); x++) {
ndp[u][(x + w * pw[i]) % P] += dp2[v][x];
}
}
dp2 = std::move(ndp);
}
Z ans = 0;
for (int u = 0; u < N; u++) {
for (int x = 0; x < std::min(pw[h], P); x++) {
int y = (X - x * pw[K - h] % P + P) % P;
if (y < pw[K - h]) {
ans += dp1[u][x] * dp2[u][y];
}
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
for (int i = 1; i <= t; i++) {
std::cout << "Case " << i << ": ";
solve();
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 35ms
memory: 9992kb
input:
100 8 10 7 2 0 6 1 0 3 1 0 5 4 0 8 2 0 6 1 0 4 3 0 7 8 0 1 6 0 6 1 0 2 6 0 5 9 2 1 0 4 5 0 3 5 0 5 4 0 5 4 0 2 3 0 4 5 0 5 4 0 4 5 0 1 4 0 10 10 6 1 0 1 7 0 9 5 0 8 2 0 7 10 0 4 10 0 6 8 0 3 4 0 4 10 0 2 10 0 5 2 0 10 9 2 1 0 4 6 0 7 5 0 3 10 0 2 9 0 9 10 0 5 10 0 8 1 0 6 10 0 1 4 0 9 10 6 2 1 7 8 0...
output:
Case 1: 216 Case 2: 25 Case 3: 0 Case 4: 5 Case 5: 0 Case 6: 0 Case 7: 0 Case 8: 1 Case 9: 0 Case 10: 0 Case 11: 0 Case 12: 5 Case 13: 0 Case 14: 120 Case 15: 0 Case 16: 0 Case 17: 0 Case 18: 99 Case 19: 0 Case 20: 5 Case 21: 6 Case 22: 2 Case 23: 0 Case 24: 6 Case 25: 19 Case 26: 0 Case 27: 21870 C...
result:
ok 100 lines
Extra Test:
score: 0
Extra Test Passed