#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; long long w = 0, k, p; bool check(vector <int> x, int k) { int n = 0, i; queue <int> q; while(x.size() > 1) { if(x.at(1) > x.at(0)) { q.push(0); } for(i = 1; i < (x.size()-1); i++) { if((x.at(i-1) > x.at(i)) || (x.at(i+1) > x.at(i))) { q.push(i); } } if(x.at(x.size()-2) > x.at(x.size()-1)) { q.push(x.size()-1); } i = 0; while(!q.empty()) { x.erase(x.begin() + q.front() - i); i++; q.pop(); } n++; } if(n == k) { return 1; } return 0; } void permute(vector <int> v, vector <int> u, int k, int p) { int i; vector <int> t1, t2; if(v.size() == 0) { if(check(u, k)) { w++; w %= p; } return; } for(i = 0; i < v.size(); i++) { t1.assign(v.begin()+1, v.end()); t2.assign(u.begin(), u.end()); t2.push_back(v.at(0)); permute(t1, t2, k, p); rotate(v.begin(), v.begin() + 1, v.end()); } } int main() { int n, i, k, p; vector <int> v, u; cin >> n >> k >> p; for(i = 1; i <= n; i++) { v.push_back(i); } permute(v, u, k, p); cout << w << "\n"; 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 | #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; long long w = 0, k, p; bool check(vector <int> x, int k) { int n = 0, i; queue <int> q; while(x.size() > 1) { if(x.at(1) > x.at(0)) { q.push(0); } for(i = 1; i < (x.size()-1); i++) { if((x.at(i-1) > x.at(i)) || (x.at(i+1) > x.at(i))) { q.push(i); } } if(x.at(x.size()-2) > x.at(x.size()-1)) { q.push(x.size()-1); } i = 0; while(!q.empty()) { x.erase(x.begin() + q.front() - i); i++; q.pop(); } n++; } if(n == k) { return 1; } return 0; } void permute(vector <int> v, vector <int> u, int k, int p) { int i; vector <int> t1, t2; if(v.size() == 0) { if(check(u, k)) { w++; w %= p; } return; } for(i = 0; i < v.size(); i++) { t1.assign(v.begin()+1, v.end()); t2.assign(u.begin(), u.end()); t2.push_back(v.at(0)); permute(t1, t2, k, p); rotate(v.begin(), v.begin() + 1, v.end()); } } int main() { int n, i, k, p; vector <int> v, u; cin >> n >> k >> p; for(i = 1; i <= n; i++) { v.push_back(i); } permute(v, u, k, p); cout << w << "\n"; return 0; } |