#include <iostream> #include <string> #include <stdio.h> #include <vector> using namespace std; unsigned long long help( unsigned int n, unsigned int k) { unsigned long long Wynik = 1; for( unsigned int i = 1; i <= k; i++) { Wynik = (Wynik * ( n - i + 1 ) / i)%(1000000007); } return (unsigned long long) Wynik; } int main() { int n; int k; cin >> n; cin >> k; char **stol=new char *[n]; for (int i = 0; i<n; i++) stol[i] = new char [n]; string str; for (int i = 0; i < n; i++) { cin >> str; str.copy(stol[i], n); } int ile_wolnych = 0; int dolnaGranica = 0; int gornaGranica = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (stol[i][j] == '#') { if (i + k + 1 < n) { if (stol[i + k + 1][j] == '.') { ile_wolnych++; stol[i + k + 1][j] = '-'; } } if (i - k - 1 >= 0) { if (stol[i - k -1][j] == '.') { ile_wolnych++; stol[i - k - 1][j] = '-'; } } dolnaGranica = j - k - 1; gornaGranica = j + k + 1; if (dolnaGranica < 0) dolnaGranica = 0; if (gornaGranica > n - 1) gornaGranica = n; for (int m = dolnaGranica; m <= gornaGranica; m++) { if (stol[i][m] == '.') { stol[i][m] = '-'; ile_wolnych++; } } for (int p = 1; p <= k; p++) { dolnaGranica = j - k - 1 + p; gornaGranica = j + k + 1 - p; if (dolnaGranica < 0) dolnaGranica = 0; if (gornaGranica > n - 1) gornaGranica = n; if (i - p >= 0) { for (int r = dolnaGranica; r <= gornaGranica; r++) { if (stol[i - p][r] == '.') { stol[i - p][r] = '-'; ile_wolnych++; } if (i + p <= n - 1) { for (int r = dolnaGranica; r <= gornaGranica; r++) { if (stol[i + p][r] == '.') { stol[i + p][r] = '-'; ile_wolnych++; } } } } } } } } } vector<int> gora; for(int i=2; i<= ile_wolnych; i++) gora.push_back(i); vector<int> dol; for(int i=2; i<=k; i++) dol.push_back(i); for(int i=2; i<=ile_wolnych-k; i++) dol.push_back(i); for(unsigned int i=0; i<dol.size(); i++){ for(unsigned int j=0; j<gora.size(); j++){ if(gora[j]%dol[i]==0){ gora[i]=gora[j]/dol[i]; } } } unsigned long long result = help(ile_wolnych,k); cout<<((result-k)%(1000000007)); return 0; }
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include <iostream> #include <string> #include <stdio.h> #include <vector> using namespace std; unsigned long long help( unsigned int n, unsigned int k) { unsigned long long Wynik = 1; for( unsigned int i = 1; i <= k; i++) { Wynik = (Wynik * ( n - i + 1 ) / i)%(1000000007); } return (unsigned long long) Wynik; } int main() { int n; int k; cin >> n; cin >> k; char **stol=new char *[n]; for (int i = 0; i<n; i++) stol[i] = new char [n]; string str; for (int i = 0; i < n; i++) { cin >> str; str.copy(stol[i], n); } int ile_wolnych = 0; int dolnaGranica = 0; int gornaGranica = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (stol[i][j] == '#') { if (i + k + 1 < n) { if (stol[i + k + 1][j] == '.') { ile_wolnych++; stol[i + k + 1][j] = '-'; } } if (i - k - 1 >= 0) { if (stol[i - k -1][j] == '.') { ile_wolnych++; stol[i - k - 1][j] = '-'; } } dolnaGranica = j - k - 1; gornaGranica = j + k + 1; if (dolnaGranica < 0) dolnaGranica = 0; if (gornaGranica > n - 1) gornaGranica = n; for (int m = dolnaGranica; m <= gornaGranica; m++) { if (stol[i][m] == '.') { stol[i][m] = '-'; ile_wolnych++; } } for (int p = 1; p <= k; p++) { dolnaGranica = j - k - 1 + p; gornaGranica = j + k + 1 - p; if (dolnaGranica < 0) dolnaGranica = 0; if (gornaGranica > n - 1) gornaGranica = n; if (i - p >= 0) { for (int r = dolnaGranica; r <= gornaGranica; r++) { if (stol[i - p][r] == '.') { stol[i - p][r] = '-'; ile_wolnych++; } if (i + p <= n - 1) { for (int r = dolnaGranica; r <= gornaGranica; r++) { if (stol[i + p][r] == '.') { stol[i + p][r] = '-'; ile_wolnych++; } } } } } } } } } vector<int> gora; for(int i=2; i<= ile_wolnych; i++) gora.push_back(i); vector<int> dol; for(int i=2; i<=k; i++) dol.push_back(i); for(int i=2; i<=ile_wolnych-k; i++) dol.push_back(i); for(unsigned int i=0; i<dol.size(); i++){ for(unsigned int j=0; j<gora.size(); j++){ if(gora[j]%dol[i]==0){ gora[i]=gora[j]/dol[i]; } } } unsigned long long result = help(ile_wolnych,k); cout<<((result-k)%(1000000007)); return 0; } |