QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#790870 | #9488. Do Not Turn Back | k1nsom# | WA | 1ms | 3872kb | C++14 | 6.1kb | 2024-11-28 15:48:53 | 2024-11-28 15:48:55 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <deque>
#include <map>
#include <vector>
#include <list>
#include <functional>
#include <stack>
#include <unordered_map>
#include <set>
#include <cctype>
#include <cstring>
#include <tuple>
#include <bitset>
#include <unordered_set>
#include <iomanip>
#include <utility>
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define us unsigned short
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)
#define XOR(a, b) ((a && !b) || (!a && b))
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef unsigned int uint;
const int M = 1e9, N = 1e3 + 3, LOGN = log2(N - 1) + 2, MOD = 45989;
const ll LM = 1e18;
int YI = 1, LING = 0;
template <typename T>
struct jvzheng
{
int n, m;
vector<vector<T>> a;
inline jvzheng(int n, int m) noexcept : n(n), m(m)
{
a.resize(n);
for (auto &i : a)
i.resize(m);
}
jvzheng(int n, int m, vector<vector<T>> a) noexcept : n(n), m(m), a(a) {}
jvzheng(int n) noexcept : n(n), m(n)
{
a.resize(n);
for (auto &i : a)
i.resize(n);
for (int i = 0; i < n; i++)
{
a[i][i] = 1;
for (int j = i + 1; j < n; j++)
{
a[i][j] = a[j][i] = 0;
}
}
}
jvzheng(const jvzheng &b) noexcept : n(b.n), m(b.m), a(b.a) {}
inline jvzheng<T> operator*(const jvzheng<T> &b) noexcept
{
if (m != b.n)
exit(1);
jvzheng<T> ans(n, b.m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < b.m; j++)
{
for (int k = 0; k < m; k++)
{
ans.a[i][j] += a[i][k] * b.a[k][j];
}
ans.a[i][j] %= MOD;
}
}
return ans;
}
inline void operator=(const jvzheng<T> &&b) noexcept
{
n = b.n;
m = b.m;
a = b.a;
}
void operator=(const jvzheng<T> &b) noexcept
{
n = b.n;
m = b.m;
a = b.a;
}
inline void operator+=(const jvzheng<T> &&b) noexcept
{
if (n != b.n || m != b.m)
exit(1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < b.m; j++)
{
a[i][j] = a[i][j] + b.a[i][j];
}
}
}
void operator+=(const jvzheng<T> &b) noexcept
{
if (n != b.n || m != b.m)
exit(1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < b.m; j++)
{
a[i][j] = a[i][j] + b.a[i][j];
}
}
}
jvzheng<T> operator+(const jvzheng<T> &&b) noexcept
{
if (n != b.n || m != b.m)
exit(1);
jvzheng<T> ans(n, b.m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < b.m; j++)
{
ans.a[i][j] = a[i][j] + b.a[i][j];
}
}
return ans;
}
inline jvzheng<T> operator+(const jvzheng<T> &b) noexcept
{
if (n != b.n || m != b.m)
exit(1);
jvzheng<T> ans(n, b.m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < b.m; j++)
{
ans.a[i][j] = a[i][j] + b.a[i][j];
}
}
return ans;
}
void out_he()
{
T ans = 0;
for (int i = 0; i < n; i++)
{
ans = ans + a[i][i];
}
cout << (ans + MOD) % MOD;
}
};
template <typename T>
struct jvjvzheng
{
int n, m, l;
vector<vector<jvzheng<T>>> a;
inline jvjvzheng(const jvjvzheng &b) noexcept : n(b.n), m(b.m), a(b.a) {}
jvjvzheng(int n, int m, int l, vector<vector<jvzheng<T>>> a) noexcept : n(n), m(m), l(l), a(a) {}
jvjvzheng(int n, int m, int l) noexcept : n(n), m(m), l(l)
{
vector<jvzheng<T>> ca(m, jvzheng<T>(l, l));
a.insert(a.end(), n, ca);
}
inline jvjvzheng<T> operator*(const jvjvzheng<T> &b) noexcept
{
if (m != b.n)
exit(1);
jvjvzheng<T> ans(n, b.m, l);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < b.m; j++)
{
for (int k = 0; k < m; k++)
{
ans.a[i][j] += a[i][k] * b.a[k][j];
}
}
}
return ans;
}
inline void operator=(const jvjvzheng<T> &&b) noexcept
{
n = b.n;
m = b.m;
a = b.a;
}
void operator=(const jvjvzheng<T> &b) noexcept
{
n = b.n;
m = b.m;
a = b.a;
}
};
template <typename T>
jvjvzheng<T> km(jvjvzheng<T> ans, jvjvzheng<T> b, int t) noexcept
{
while (t)
{
if (t & 1)
ans = ans * b;
b = b * b;
t >>= 1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);
int n, m, k, a, b;
cin >> n >> m >> k; //>> a >> b;
a = 0, b = n - 1;
jvzheng<ll> x(n, n), y(n, n);
int u, v;
while (m--)
{
cin >> u >> v;
u--, v--;
x.a[u][v]++, x.a[v][u]++;
y.a[u][u]--, y.a[v][v]--;
}
vector<vector<jvzheng<ll>>> va, vb;
va.resize(1);
jvzheng<ll> xx((x * x) + y);
for (int i = 0; i < n; i++)
y.a[i][i]++;
va.front().push_back(x), va.front().push_back(xx);
vb.resize(2);
vb.front().push_back(jvzheng<ll>(n, n)), vb.front().push_back(y);
vb.back().push_back(jvzheng<ll>(n)), vb.back().push_back(x);
cout << (km(jvjvzheng<ll>(1, 2, n, va), jvjvzheng<ll>(2, 2, n, vb), k - 1).a[0][0].a[a][b] + MOD) % MOD;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3672kb
input:
6 8 5 1 2 1 3 2 3 2 4 3 5 4 5 4 6 5 6
output:
2
result:
ok "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
11 11 2023 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 1 11
output:
1
result:
ok "1"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3872kb
input:
7 21 1000000000 1 2 1 3 1 4 1 5 1 6 1 7 2 3 2 4 2 5 2 6 2 7 3 4 3 5 3 6 3 7 4 5 4 6 4 7 5 6 5 7 6 7
output:
34707
result:
wrong answer 1st words differ - expected: '405422475', found: '34707'