fork(1) download
copy 
  1. // karanaggarwal
  2. #include<bits/stdc++.h>
  3. #define PB push_back
  4. #define MP make_pair
  5. #define F first
  6. #define S second
  7. #define SZ(a) (int)(a.size())
  8. #define SET(a,b) memset(a,b,sizeof(a))
  9. #define LET(x,a) __typeof(a) x(a)
  10. #define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
  11. #define repi(i,n) for(int i=0; i<(int)n;i++)
  12. #define si(n) scanf("%d",&n)
  13. #define sll(n) scanf("%lld",&n)
  14. #define sortv(a) sort(a.begin(),a.end())
  15. #define all(a) a.begin(),a.end()
  16. #define DRT()  int t; cin>>t; while(t--)
  17. #define TRACE
  18. using namespace std;
  19.  
  20. //FILE *fin = freopen("in","r",stdin);
  21. //FILE *fout = freopen("out","w",stdout);
  22.  
  23.  
  24. #ifdef TRACE
  25. #define trace1(x)                cerr << #x << ": " << x << endl;
  26. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  27. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  28. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  29. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  30. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  31.  
  32. #else
  33.  
  34. #define trace1(x)
  35. #define trace2(x, y)
  36. #define trace3(x, y, z)
  37. #define trace4(a, b, c, d)
  38. #define trace5(a, b, c, d, e)
  39. #define trace6(a, b, c, d, e, f)
  40.  
  41. #endif
  42.  
  43.  
  44. typedef long long LL;
  45. typedef pair<int,int> PII;
  46. typedef vector<int> VI;
  47. typedef vector< PII > VPII;
  48.  
  49. #define mod 1000000007
  50.  
  51. LL A[31][31];
  52. LL ret[31][31];
  53. LL og[31][31];
  54. int N; 
  55.  
  56. void mul(LL A[][31], LL B[][31])
  57. {
  58.     LL C[31][31];
  59.     repi(i,N)
  60.         repi(j,N)
  61.         {
  62.             C[i][j] = 0;
  63.             repi(k,N)
  64.                 C[i][j] += (A[i][k]*B[k][j]) % mod;
  65.         }
  66.     repi(i,N)
  67.         repi(j,N)
  68.             A[i][j] = C[i][j]%mod;
  69. }
  70.  
  71. void power(LL A[][31], LL P)
  72. {
  73.     SET(ret,0); for(int i=0; i<N;i++)ret[i][i] = 1;
  74.     while(P)
  75.     {
  76.         if(P&1)
  77.             mul(ret,A);
  78.         mul(A,A); P/=2;
  79.     }
  80.  
  81. }
  82.  
  83. LL ans[30][31][31];
  84.  
  85. int main()
  86. {
  87.     int M;
  88.     cin>>N>>M;
  89.     LL K;
  90.     cin>>K; int x,y;
  91.     K++;
  92.     while(M--)
  93.     {
  94.         si(x); si(y); x--; y--; A[x][y]++;
  95.     }
  96.     N++;
  97.     repi(i,N)repi(j,N)og[i][j] = A[i][j];
  98.  
  99.     for(int dest = 0; dest<N-1; dest++)
  100.     {
  101.         repi(i,N)repi(j,N)A[i][j] = og[i][j];
  102.         int y = dest; 
  103.         A[y][N-1] = 1; A[N-1][N-1] = 1;
  104.         power(A,K);
  105.         repi(i,N)repi(j,N)ans[dest][i][j] = ret[i][j];
  106.         ans[y][y][N-1]--; if(ans[y][y][N-1]<0)ans[y][y][N-1]++;
  107.     }
  108.  
  109.     int q; si(q); while(q--)
  110.     {
  111.         int x,y; si(x); si(y); x--; y--; 
  112.         printf("%lld\n", ans[y][x][N-1]);
  113.     }
  114.     return 0;
  115. }
  116.  
  117.  
Runtime error #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BozOtW
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!