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