This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://yukicoder.me/problems/no/1750"
#include "head.hpp"
#include "math/matrix.hpp"
#include "io/Scanner.hpp"
#include "io/Printer.hpp"
Scanner scanner;
Printer printer;
int main()
{
int n, m;
i64 T;
scanner.scan(n, m, T);
matrix<i64> a(n, n);
for(int i = 1;i <= m;i++)
{
int s, t;
scanner.scan(s, t);
s++, t++;
a.m[s][t] = a.m[t][s] = 1;
}
a = a.pow(T);
printer.println(a.m[1][1]);
}#line 1 "test/yukicoder/1750.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1750"
#line 1 "head.hpp"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define CLOCK 1e3 * clock() / CLOCKS_PER_SEC
#line 2 "math/matrix.hpp"
using i64 = long long;
constexpr i64 P = 998244353;
constexpr int mmax = 2000;
template<typename T>
struct matrix
{
int row, col;
i64 m[mmax][mmax];
matrix(int r, int c): row(r), col(c) {memset(m, 0, sizeof(m));}
matrix(int r, int c, int val): row(r), col(c)
{
memset(m, 0, sizeof(m));
for(int i = 1;i <= row;i++)
for(int j = 1;j <= col;j++)
m[i][j] = val;
}
matrix(int r, int c, std::vector<std::vector<T>> _m): row(r), col(c)
{
memset(m, 0, sizeof(m));
for(int i = 1;i <= row;i++)
for(int j = 1;j <= col;j++)
m[i][j] = _m[i][j];
}
matrix operator *= (const matrix &rhs)
{
assert(col == rhs.row);
i64 tmp[mmax][mmax];
memset(tmp, 0, sizeof(tmp));
for(int k = 1;k <= col;k++)
for(int i = 1;i <= row;i++)
for(int j = 1;j <= rhs.col;j++)
tmp[i][j] = (tmp[i][j] + ((m[i][k] * rhs.m[k][j]))) % P;
memcpy(m, tmp, sizeof(tmp));
return *this;
}
friend matrix operator *(const matrix &lhs, const matrix &rhs)
{
assert(lhs.col == rhs.row);
matrix res = lhs;
res *= rhs;
return res;
}
matrix<T> pow(T k)
{
assert(row == col);
k--;
matrix<T> Ans = *this, f = *this;
while(k)
{
if(k & 1)
Ans *= f;
f *= f;
k >>= 1;
}
return Ans;
}
};
#line 2 "io/Scanner.hpp"
class Scanner
{
public:
Scanner(std::FILE *f = stdin, std::size_t enough_buffer_size = 1 << 25)
: f_(f), buffer_(new char[enough_buffer_size + 32]), buffer_head_(buffer_),
buffer_tail_(buffer_ + std::fread(buffer_, sizeof(char), enough_buffer_size + 32, f_)) {*buffer_tail_ = '\0';}
~Scanner() {delete[] buffer_;}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, bool>
scan(T &x)
{
x = 0;
while(*buffer_head_ != '-' && std::isspace(*buffer_head_))
++buffer_head_;
bool is_neg = *buffer_head_ == '-' && ++buffer_head_;
char *old_buffer_head = buffer_head_;
if(is_neg)
while(std::isdigit(*buffer_head_)) x = x * 10 - (*buffer_head_++ - '0');
else
while(std::isdigit(*buffer_head_)) x = x * 10 + (*buffer_head_++ - '0');
return buffer_head_ != old_buffer_head;
}
template<typename... T>
bool scan(T &...x)
{
return (... && scan(x));
}
private:
std::FILE *f_;
char *buffer_, *buffer_head_, *buffer_tail_;
};
#line 2 "io/Printer.hpp"
class Printer
{
public:
Printer(std::FILE *f = stdout, std::size_t buffer_size = 100000)
: f_(f), buffer_(new char[buffer_size + 32]), buffer_head_(buffer_),
buffer_end_(buffer_ + buffer_size + 32), stk_(new char[32]), top_(stk_) {}
~Printer()
{
flush();
delete[] stk_;
delete[] buffer_;
}
void flush()
{
std::fwrite(buffer_, buffer_head_ - buffer_, sizeof(char), f_);
buffer_head_ = buffer_;
}
void putchar(char x)
{
if(buffer_end_ == buffer_head_)
flush();
*buffer_head_++ = x;
}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, void>
print(T x)
{
if(x == 0)
return this->putchar('0');
if(x < 0)
{
putchar('-');
do
{
T y = x / 10;
*top_++ = y * 10 - x + '0';
x = y;
} while(x != 0);
}
else
{
do
{
T y = x / 10;
*top_++ = x - y * 10 + '0';
x = y;
} while(x != 0);
}
if(buffer_end_ - buffer_head_ < top_ - stk_)
flush();
while(top_ != stk_) *buffer_head_++ = *--top_;
}
void print(char x) {return this->putchar(x);}
template<typename T>
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_unsigned_v<T>, void>
print(T x)
{
if(x == 0)
return this->putchar('0');
do
{
T y = x / 10;
*top_++ = x - y * 10 + '0';
x = y;
} while(x != 0);
if(buffer_end_ - buffer_head_ < top_ - stk_)
flush();
while(top_ != stk_) *buffer_head_++ = *--top_;
}
template<typename... T>
void print(T... x)
{
return (..., print(x));
}
template<typename T>
void println(T x)
{
return this->print(x), this->putchar('\n');
}
private:
std::FILE *f_;
char *buffer_, *buffer_head_, *buffer_end_, *stk_, *top_;
};
#line 6 "test/yukicoder/1750.test.cpp"
Scanner scanner;
Printer printer;
int main()
{
int n, m;
i64 T;
scanner.scan(n, m, T);
matrix<i64> a(n, n);
for(int i = 1;i <= m;i++)
{
int s, t;
scanner.scan(s, t);
s++, t++;
a.m[s][t] = a.m[t][s] = 1;
}
a = a.pow(T);
printer.println(a.m[1][1]);
}