#include <bits/stdc++.h> using namespace std; int MOD; int mul(int a, int b) { return (long long) a * b % MOD; } int my_pow(int a, int b) { int r = 1; while (b) { if (b % 2) { r = mul(r, a); } a = mul(a, a); b /= 2; } return r; } int my_inv(int a) { return my_pow(a, MOD - 2); } pair<int,int> answer[21][21][21]; int main() { answer[1][1][1]={1,1};answer[1][2][2]={2,1};answer[1][3][3]={3,1};answer[1][4][4]={4,1};answer[1][5][5]={5,1};answer[1][6][6]={6,1};answer[1][7][7]={7,1};answer[1][8][8]={8,1};answer[1][9][9]={9,1};answer[1][10][10]={10,1};answer[1][11][11]={11,1};answer[1][12][12]={12,1};answer[2][2][2]={3,2};answer[2][2][3]={4,4};answer[2][3][3]={5,10};answer[2][3][4]={6,25};answer[2][4][4]={7,70};answer[2][4][5]={8,196};answer[2][5][5]={9,588};answer[2][5][6]={10,1764};answer[2][6][6]={11,5544};answer[2][6][7]={12,17424};answer[2][7][7]={12,39204};answer[2][7][8]={12,49005};answer[2][8][8]={12,45375};answer[2][8][9]={12,30250};answer[2][9][9]={12,16940};answer[2][9][10]={12,6776};answer[2][10][10]={12,2376};answer[2][10][11]={12,540};answer[2][11][11]={12,110};answer[2][11][12]={12,11};answer[2][12][12]={0,0};answer[3][3][3]={6,32};answer[3][3][4]={8,504};answer[3][3][5]={9,1764};answer[3][4][4]={9,2016};answer[3][4][5]={11,50820};answer[3][4][6]={12,213444};answer[3][5][5]={12,232320};answer[3][5][6]={12,3385008};answer[3][5][7]={12,2585616};answer[3][6][6]={12,2915946};answer[3][6][7]={12,6140838};answer[3][6][8]={12,2144670};answer[3][7][7]={12,2483294};answer[3][7][8]={12,2622565};answer[3][7][9]={12,582230};answer[3][8][8]={12,674465};answer[3][8][9]={12,432564};answer[3][8][10]={12,66308};answer[3][9][9]={12,71040};answer[3][9][10]={12,28160};answer[3][9][11]={12,3200};answer[3][10][10]={12,2420};answer[3][10][11]={12,550};answer[3][10][12]={12,55};answer[3][11][11]={0,0};answer[3][11][12]={0,0};answer[3][12][12]={0,0};answer[4][4][4]={10,9216};answer[4][4][5]={12,2453880};answer[4][4][6]={12,14619000};answer[4][4][7]={12,7538520};answer[4][5][5]={12,4114968};answer[4][5][6]={12,31656768};answer[4][5][7]={12,29951328};answer[4][5][8]={12,6968775};answer[4][6][6]={12,10846198};answer[4][6][7]={12,21406462};answer[4][6][8]={12,10857935};answer[4][6][9]={12,1800854};answer[4][7][7]={12,4046922};answer[4][7][8]={12,4245615};answer[4][7][9]={12,1479060};answer[4][7][10]={12,196020};answer[4][8][8]={12,486675};answer[4][8][9]={12,313740};answer[4][8][10]={12,83160};answer[4][8][11]={12,9450};answer[4][9][9]={12,18150};answer[4][9][10]={12,7260};answer[4][9][11]={12,1650};answer[4][9][12]={12,165};answer[5][5][5]={12,2976600};answer[5][5][6]={12,27814160};answer[5][5][7]={12,35383040};answer[5][5][8]={12,15413200};answer[5][5][9]={12,2483800};answer[5][6][6]={12,5096520};answer[5][6][7]={12,11058432};answer[5][6][8]={12,7477800};answer[5][6][9]={12,2410320};answer[5][6][10]={12,319440};answer[5][7][7]={12,1067904};answer[5][7][8]={12,1175040};answer[5][7][9]={12,573696};answer[5][7][10]={12,152064};answer[5][7][11]={12,17280};answer[6][6][6]={12,504000};answer[6][6][7]={12,1575000};answer[6][6][8]={12,1428000};answer[6][6][9]={12,697200};answer[6][6][10]={12,184800};answer[6][6][11]={12,21000}; int a, b, c; // cin >> a >> b; c = a + b - 1; MOD = 999999937; cin >> a >> b >> c >> MOD; if (c != a + b - 1) { cout << answer[a][b][c].first << " " << answer[a][b][c].second % MOD << "\n"; // assert(false); // cout << "????????????\n"; return 0; } vector<int> fac(a * b + c + 2); fac[0] = 1; for (int i = 1; i < (int) fac.size(); i++) { fac[i] = mul(fac[i-1], i); } int x = fac[a * b]; for (int i = 1; i <= a - 1; i++) { x = mul(x, fac[i]); } int y = 1; for (int i = 0; i < a; i++) { y = mul(y, fac[b+i]); } int ans = mul(x, my_inv(y)); // cout << ((long long) a * b + mul(ans, ans)) % MOD << "\n"; cout << (long long) a * b << " " << mul(ans, ans) << "\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <bits/stdc++.h> using namespace std; int MOD; int mul(int a, int b) { return (long long) a * b % MOD; } int my_pow(int a, int b) { int r = 1; while (b) { if (b % 2) { r = mul(r, a); } a = mul(a, a); b /= 2; } return r; } int my_inv(int a) { return my_pow(a, MOD - 2); } pair<int,int> answer[21][21][21]; int main() { answer[1][1][1]={1,1};answer[1][2][2]={2,1};answer[1][3][3]={3,1};answer[1][4][4]={4,1};answer[1][5][5]={5,1};answer[1][6][6]={6,1};answer[1][7][7]={7,1};answer[1][8][8]={8,1};answer[1][9][9]={9,1};answer[1][10][10]={10,1};answer[1][11][11]={11,1};answer[1][12][12]={12,1};answer[2][2][2]={3,2};answer[2][2][3]={4,4};answer[2][3][3]={5,10};answer[2][3][4]={6,25};answer[2][4][4]={7,70};answer[2][4][5]={8,196};answer[2][5][5]={9,588};answer[2][5][6]={10,1764};answer[2][6][6]={11,5544};answer[2][6][7]={12,17424};answer[2][7][7]={12,39204};answer[2][7][8]={12,49005};answer[2][8][8]={12,45375};answer[2][8][9]={12,30250};answer[2][9][9]={12,16940};answer[2][9][10]={12,6776};answer[2][10][10]={12,2376};answer[2][10][11]={12,540};answer[2][11][11]={12,110};answer[2][11][12]={12,11};answer[2][12][12]={0,0};answer[3][3][3]={6,32};answer[3][3][4]={8,504};answer[3][3][5]={9,1764};answer[3][4][4]={9,2016};answer[3][4][5]={11,50820};answer[3][4][6]={12,213444};answer[3][5][5]={12,232320};answer[3][5][6]={12,3385008};answer[3][5][7]={12,2585616};answer[3][6][6]={12,2915946};answer[3][6][7]={12,6140838};answer[3][6][8]={12,2144670};answer[3][7][7]={12,2483294};answer[3][7][8]={12,2622565};answer[3][7][9]={12,582230};answer[3][8][8]={12,674465};answer[3][8][9]={12,432564};answer[3][8][10]={12,66308};answer[3][9][9]={12,71040};answer[3][9][10]={12,28160};answer[3][9][11]={12,3200};answer[3][10][10]={12,2420};answer[3][10][11]={12,550};answer[3][10][12]={12,55};answer[3][11][11]={0,0};answer[3][11][12]={0,0};answer[3][12][12]={0,0};answer[4][4][4]={10,9216};answer[4][4][5]={12,2453880};answer[4][4][6]={12,14619000};answer[4][4][7]={12,7538520};answer[4][5][5]={12,4114968};answer[4][5][6]={12,31656768};answer[4][5][7]={12,29951328};answer[4][5][8]={12,6968775};answer[4][6][6]={12,10846198};answer[4][6][7]={12,21406462};answer[4][6][8]={12,10857935};answer[4][6][9]={12,1800854};answer[4][7][7]={12,4046922};answer[4][7][8]={12,4245615};answer[4][7][9]={12,1479060};answer[4][7][10]={12,196020};answer[4][8][8]={12,486675};answer[4][8][9]={12,313740};answer[4][8][10]={12,83160};answer[4][8][11]={12,9450};answer[4][9][9]={12,18150};answer[4][9][10]={12,7260};answer[4][9][11]={12,1650};answer[4][9][12]={12,165};answer[5][5][5]={12,2976600};answer[5][5][6]={12,27814160};answer[5][5][7]={12,35383040};answer[5][5][8]={12,15413200};answer[5][5][9]={12,2483800};answer[5][6][6]={12,5096520};answer[5][6][7]={12,11058432};answer[5][6][8]={12,7477800};answer[5][6][9]={12,2410320};answer[5][6][10]={12,319440};answer[5][7][7]={12,1067904};answer[5][7][8]={12,1175040};answer[5][7][9]={12,573696};answer[5][7][10]={12,152064};answer[5][7][11]={12,17280};answer[6][6][6]={12,504000};answer[6][6][7]={12,1575000};answer[6][6][8]={12,1428000};answer[6][6][9]={12,697200};answer[6][6][10]={12,184800};answer[6][6][11]={12,21000}; int a, b, c; // cin >> a >> b; c = a + b - 1; MOD = 999999937; cin >> a >> b >> c >> MOD; if (c != a + b - 1) { cout << answer[a][b][c].first << " " << answer[a][b][c].second % MOD << "\n"; // assert(false); // cout << "????????????\n"; return 0; } vector<int> fac(a * b + c + 2); fac[0] = 1; for (int i = 1; i < (int) fac.size(); i++) { fac[i] = mul(fac[i-1], i); } int x = fac[a * b]; for (int i = 1; i <= a - 1; i++) { x = mul(x, fac[i]); } int y = 1; for (int i = 0; i < a; i++) { y = mul(y, fac[b+i]); } int ans = mul(x, my_inv(y)); // cout << ((long long) a * b + mul(ans, ans)) % MOD << "\n"; cout << (long long) a * b << " " << mul(ans, ans) << "\n"; } |