Untitled
unknown
plain_text
9 months ago
6.6 kB
4
Indexable
#include <iostream> #include <bits/stdc++.h> // policy based datastructure // #include <ext/pb_ds/assoc_container.hpp> // // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // #define indexed_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define ll long long // #define ll int #define en '\n' #define ff first #define ss second #define pb push_back #define MP make_pair #define mod 1000000007 #define mod2 998244353 #define fast \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; typedef vector<ll> vi; typedef vector<vi> vvi; typedef priority_queue<ll> pqi; typedef priority_queue<ll, vi, greater<ll>> minpqi; typedef pair<ll, ll> pii; #define debarr(a, n) \ cout << #a << " : "; \ for (int i = 0; i < n; i++) \ cerr << a[i] << " "; \ cerr << endl; #define debmat(mat, row, col) \ cout << #mat << " :\n"; \ for (int i = 0; i < row; i++) \ { \ for (int j = 0; j < col; j++) \ cerr << mat[i][j] << " "; \ cerr << endl; \ } #define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__) template <class S, class T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << "(" << p.first << ", " << p.second << ")"; } template <class T> ostream &operator<<(ostream &os, const vector<T> &p) { os << "[ "; for (auto &it : p) os << it << " "; return os << "]"; } template <class T> ostream &operator<<(ostream &os, const unordered_set<T> &p) { os << "[ "; for (auto &it : p) os << it << " "; return os << "]"; } template <class S, class T> ostream &operator<<(ostream &os, const unordered_map<S, T> &p) { os << "[ "; for (auto &it : p) os << it << " "; return os << "]"; } template <class T> ostream &operator<<(ostream &os, const set<T> &p) { os << "[ "; for (auto &it : p) os << it << " "; return os << "]"; } template <class T> ostream &operator<<(ostream &os, const multiset<T> &p) { os << "[ "; for (auto &it : p) os << it << " "; return os << "]"; } template <class S, class T> ostream &operator<<(ostream &os, const map<S, T> &p) { os << "[ "; for (auto &it : p) os << it << " "; return os << "]"; } template <class T> void dbs(string str, T t) { cerr << str << " : " << t << "\n"; } template <class T, class... S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...); } template <class T> void prc(T a, T b) { cerr << "["; for (T i = a; i != b; ++i) { if (i != a) cerr << ", "; cerr << *i; } cerr << "]\n"; } #define all(x) x.begin(), x.end() #define present(c, key) (find(all(c), key) != c.end()) #define tr(c, it) for (auto it : c) #define fr(i, s, e) for (ll i = s; i < e; i++) #define revfr(i, s, e) for (ll i = s - 1; i >= e; i--) #define getv(v, n) \ for (ll i = 0; i < n; i++) \ cin >> v[i]; template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { for (auto element : v) { os << element << ' '; } return os; } template <typename T> istream &operator>>(istream &ins, vector<T> &v) { int sz = v.size(); for (int i = 0; i < sz; i++) ins >> v[i]; return ins; } inline void add(ll &a, ll b) { a += b; if (a >= mod) a -= mod; } inline void sub(ll &a, ll b) { a -= b; if (a < 0) a += mod; } inline ll mul(ll a, ll b, ll p = mod) { return (ll)((long long)a * b % p); } inline ll power(ll a, long long b, ll p = mod) { ll res = 1; while (b > 0) { if (b & 1) { res = mul(res, a, p); } a = mul(a, a, p); b >>= 1; } return res; } inline ll binpow(ll a, long long b) { ll res = 1; while (b > 0) { if (b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; } inline ll inv(ll a, ll p = mod) { a %= p; if (a < 0) a += p; ll b = p, u = 0, v = 1; while (a) { ll t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } if (u < 0) u += p; return u; } // inline ll lsb(ll x) // { // return x&(~(x-1)); // } // ll modexp2(ll a, ll b, ll c, ll p) // calculate (a^(b^c))%prime // { // // By Fermat's Little Theorem (a^(p-1))%p = 1 if p is prime // ll x = power(b,c,p-1); // so we first find remainder when b^c is divided by p-1 // return (power(a,x,p)); // then just do (a^remainder)%p // } ll gcd(ll a, ll b) { if (a == 0 or b == 0) return a ^ b; return gcd(b, a % b); } ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); } void fread() { // #ifdef freopen("./input.txt", "r", stdin); freopen("./output.txt", "w", stdout); // #endif } vvi& operator*(vvi &a,vvi &b){ ll n=a.size(),m=a[0].size(),p=b[0].size(); vvi c(n,vi(p,0)); fr(i,0,n){ fr(j,0,p){ fr(k,0,m) { c[i][j]+=(a[i][k]*b[k][j])%mod; if(c[i][j]>=mod)c[i][j]-=mod; } } } fr(i,0,n)fr(j,0,p)a[i][j]=c[i][j]; // return c; return a; } ostream &operator<<(ostream &os,vvi &a){ for(auto x:a){ for(auto y:x){ os<<y<<" "; } os<<"\n"; } return os; } vvi dist; ll n; ll path(ll k){ vvi ans(n,vi(n,0)); fr(i,0,n)ans[i][i]=1; while(k){ if(k&1){ ans=(ans*dist); } k/=2; dist=(dist*dist); } return ans[0][n-1]; } void solve() { ll m,k; cin>>n>>m>>k; dist.clear(); dist.assign(n,vi(n,0)); fr(i,0,m){ ll a,b; cin>>a>>b; a--,b--; dist[a][b]=1; } cout<<path(k)<<"\n"; } using namespace std; int main() { fast // pre(); // fread(); ll _t = 1; // cin >> _t; fr(i, 1, _t + 1) { // cerr<<"i="<<i<<en; solve(); } return 0; }
Editor is loading...
Leave a Comment