結果
問題 | No.1749 ラムドスウイルスの感染拡大 |
ユーザー |
![]() |
提出日時 | 2021-11-19 21:29:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 5,213 bytes |
コンパイル時間 | 1,418 ms |
コンパイル使用メモリ | 136,316 KB |
最終ジャッジ日時 | 2025-01-25 19:58:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <algorithm>#include <cassert>#include <climits>#include <cmath>#include <iostream>#include <iterator>#include <map>#include <numeric>#include <queue>#include <set>#include <unordered_map>#include <unordered_set>#include <vector>#include <random>#include <complex>#include <bitset>#include <iomanip>#include <memory>#include <chrono>#include <functional>#define rep(i, n, s) for(int i = (s); i < int(n); i++)#define per(i, n, s) for(int i = (n - 1); i >= int(s); i--)#define MM << " " <<#define all(x) x.begin(), x.end()#define rall(x) rbegin(x), rend(x)template <class T>using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;template <class T>using MaxHeap = std::priority_queue<T>;using ll = long long;using Pii = std::pair<int, int>;using Pll = std::pair<ll, ll>;using Pdd = std::pair<double, double>;template <class T>bool chmin(T &a, const T b) {if (a > b) {a = b;return true;} else {return false;}}template <class T>bool chmax(T &a, const T b) {if (a < b) {a = b;return true;} else {return false;}}template <class T>void vdeb(const std::vector<T> &da) {auto n = da.size();for (size_t i = 0; i < n; i++) {if (i == n - 1)std::cout << da[i];elsestd::cout << da[i] << " ";}std::cout << std::endl;}template<class T>void vdeb(const std::vector<std::vector<T>> &da) {auto n = da.size();for (size_t i = 0; i < n; i++) {std::cout << i << " : ";vdeb(da[i]);}std::cout << std::endl;}template <>void vdeb(const std::vector<std::string> &da) {auto n = da.size();for (size_t i = 0; i < n; i++) { std::cout << da[i] << std::endl; }}struct modint {long long num;const static long long p = 998244353;constexpr static long long pow(long long n, long long k) {//n^k(mod p)long long ret = 1;while(k) {if(k&1) ret = ret * n % p;n = n * n % p;k >>= 1;}return ret;}// a*A + b*B = 1constexpr static void euclid(long long &a, long long &b) { // a>=b A*b+B*(a-a/b*b)=1if (a == 1) {a = 1;}else {long long A = b, B = a % b;euclid(A, B);b = (A - (p + a / b) % p * B % p + p) % p;a = B;}}constexpr static long long rev(const long long n) {// n*x-p*y=1//long long q = p;//euclid(p, n, p);//return n % q;return pow(n,p-2);}constexpr modint() : num(0) {}constexpr modint(long long x) : num(x%p < 0 ? x%p+p : x%p) {}constexpr modint inv() const {return rev(num);}modint operator-() const {return modint(p-num);}modint& operator+=(const modint &other){num = (num + other.num) % p;return *this;}modint& operator-=(const modint &other){num = (num - other.num + p) % p;return *this;}modint& operator*=(const modint &other){num = (num * other.num) % p;return *this;}modint& operator/=(const modint &other){(*this) *= other.inv();return *this;}modint& operator+=(const long long &other){num = (num + other) % p;return *this;}modint& operator-=(const long long &other){num = (num - other + p) % p;return *this;}modint& operator*=(const long long &other){num = (num * other) % p;return *this;}modint& operator/=(const long long &other){(*this) *= rev(other);return *this;}modint& operator++(){return *this += 1;}modint& operator--(){return *this -= 1;}modint& operator=(const long long &other){return (*this) = modint(other);}modint operator+(const modint &other) const{return modint(*this) += other;}modint operator-(const modint &other) const{return modint(*this) -= other;}modint operator*(const modint &other) const{return modint(*this) *= other;}modint operator/(const modint &other) const{return modint(*this) /= other;}modint operator+(const long long &other) const{return modint(*this) += other;}modint operator-(const long long &other) const{return modint(*this) -= other;}modint operator*(const long long &other) const{return modint(*this) *= other;}modint operator/(const long long &other) const{return modint(*this) /= other;}bool operator==(const modint &other) const{return num == other.num;}};std::istream& operator>>(std::istream &is, modint x) {is >> x.num;return is;}std::ostream& operator<<(std::ostream &os, const modint &x){os << x.num;return os;}using namespace std;int main() {int n, m, t; cin >> n >> m >> t;vector<Pii> da(m);rep(i,m,0) cin >> da[i].first >> da[i].second;vector<modint> dp(n);dp[0] += 1;rep(i,t,0) {vector<modint> tmp(n);for(auto &i : da) {tmp[i.first] += dp[i.second];tmp[i.second] += dp[i.first];}swap(dp, tmp);}cout << dp[0] << endl;}