fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int K = 1e6 + 5; 
  12. const int MOD = 998244353;  
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD; 
  17. }
  18.  
  19. int h, w, k;  
  20. int sx, sy, tx, ty; 
  21.  
  22. int dp[K][2][2]; // dp[i][0/1][0/1] = Số cách đi của quân xe khi xét đến nước đi thứ i
  23. 				 // 				  ô hiện tại của quân xe có đang cùng hàng với ô đích hay không? 
  24. 				 // 				  ô hiện tại của quân xe có đang cùng cột với ô đích hay không?
  25.  
  26. int main() {
  27. 	ios::sync_with_stdio(false); 
  28. 	cin.tie(nullptr);  	
  29. 	cin >> h >> w >> k;  
  30. 	cin >> sx >> sy >> tx >> ty; 
  31.  
  32. 	dp[0][(sx == tx)][(sy == ty)] = 1;  
  33.  
  34. 	for (int i = 1; i <= k; i++) {
  35. 		// (0, 0)
  36. 		add(dp[i][1][0], dp[i - 1][0][0]);  
  37. 		add(dp[i][0][1], dp[i - 1][0][0]); 
  38. 		add(dp[i][0][0], 1ll * dp[i - 1][0][0] * (h + w - 4) % MOD); 
  39.  
  40. 		// (1, 0)
  41. 		add(dp[i][1][0], 1ll * dp[i - 1][1][0] * (w - 2) % MOD); 
  42. 		add(dp[i][1][1], dp[i - 1][1][0]); 
  43. 		add(dp[i][0][0], 1ll * dp[i - 1][1][0] * (h - 1) % MOD); 
  44.  
  45. 		// (0, 1)
  46. 		add(dp[i][0][1], 1ll * dp[i - 1][0][1] * (h - 2) % MOD);  
  47. 		add(dp[i][1][1], dp[i - 1][0][1]); 
  48. 		add(dp[i][0][0], 1ll * dp[i - 1][0][1] * (w - 1) % MOD);
  49.  
  50. 		// (1, 1)
  51. 		add(dp[i][1][0], 1ll * dp[i - 1][1][1] * (w - 1) % MOD);  
  52. 		add(dp[i][0][1], 1ll * dp[i - 1][1][1] * (h - 1) % MOD); 
  53. 	}
  54.  
  55. 	cout << dp[k][1][1] << '\n'; 
  56. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
2 2 2
1 2 2 1
stdout
copy 
2
https://ideone.com/GtGD4b
language:
C++14 (gcc 8.3)
created:
39 days ago
visibility:
secret

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!