#include <vector> #include <algorithm> #include <iostream> using namespace std; int peaks(const vector<int> & perm) { int pks=0; if (perm[0]>perm[1]) pks++; if (perm[perm.size()-1]>perm[perm.size()-2]) pks++; for(int i=1 ; i < perm.size()-1; i++) if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++; return pks ; } vector<int> reduce(const vector<int> & perm) { if (perm.size()==1) return perm; vector<int> c; if (perm[0]>perm[1]) c.push_back(perm[0]); for(int i=1 ; i < perm.size()-1; i++) if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) c.push_back(perm[i]); if (perm[perm.size()-1]>perm[perm.size()-2]) c.push_back(perm[perm.size()-1]); return c; } int calc(vector<int> p) { int m=0; while (p.size()>1) { p=reduce(p); m++; } return m; } void show(int pks,const vector<int> & perm) { cout << pks<<" : "; for (int i=0;i<perm.size();i++) cout << perm[i]<<" "; cout << endl; } int main(int argc, char *argv[]) { int n,k,p; cin >> n >> k >>p; int answer=0; vector<int> perm(n); for(int i=0 ; i < n ; i++) perm[i]=i+1; int k1=0;int n1=n-1; while(n1) {k1++;n1/=2;} //cout<<k1<<endl; if (k>k1) {cout << 0; return 0;} if (k==1) { int n1=n-1; long long a=1; while (n1) {a=(2*a)%p; n1--;} cout << a; return 0; } if (calc(perm)==k) answer = (answer+1)%p; while ( next_permutation(perm.begin(), perm.end()) ) { //show(0,perm); if (calc(perm)==k) answer = (answer+1)%p; } cout << answer; /* int n=10; int nmax = n+1; for (; n < nmax ; n++) { const int kmax = (n+1)/2; vector<int> Tnk(kmax+1); vector<int> Tms(kmax+1); vector<int> perm(n); for(int i=0 ; i < n ; i++) perm[i]=i+1; int pks = peaks(perm); Tnk[pks]++; show(pks,perm); Tms[1]++; cout << 1 << endl; while ( next_permutation(perm.begin(), perm.end()) ) { pks = peaks(perm); //show(pks,perm); //if (pks==3) show(pks,perm); Tnk[pks]++; vector<int> p = perm; int m=0; while (p.size()>1) { p=reduce(p); m++; } Tms[m]++; //cout << m << endl; } for (int i=1; i < Tnk.size(); i++) cout << Tnk[i] << ", " ; cout << endl; for (int i=1; i < Tms.size(); i++) cout << Tms[i] << ", " ; cout << endl; } */ }
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 | #include <vector> #include <algorithm> #include <iostream> using namespace std; int peaks(const vector<int> & perm) { int pks=0; if (perm[0]>perm[1]) pks++; if (perm[perm.size()-1]>perm[perm.size()-2]) pks++; for(int i=1 ; i < perm.size()-1; i++) if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++; return pks ; } vector<int> reduce(const vector<int> & perm) { if (perm.size()==1) return perm; vector<int> c; if (perm[0]>perm[1]) c.push_back(perm[0]); for(int i=1 ; i < perm.size()-1; i++) if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) c.push_back(perm[i]); if (perm[perm.size()-1]>perm[perm.size()-2]) c.push_back(perm[perm.size()-1]); return c; } int calc(vector<int> p) { int m=0; while (p.size()>1) { p=reduce(p); m++; } return m; } void show(int pks,const vector<int> & perm) { cout << pks<<" : "; for (int i=0;i<perm.size();i++) cout << perm[i]<<" "; cout << endl; } int main(int argc, char *argv[]) { int n,k,p; cin >> n >> k >>p; int answer=0; vector<int> perm(n); for(int i=0 ; i < n ; i++) perm[i]=i+1; int k1=0;int n1=n-1; while(n1) {k1++;n1/=2;} //cout<<k1<<endl; if (k>k1) {cout << 0; return 0;} if (k==1) { int n1=n-1; long long a=1; while (n1) {a=(2*a)%p; n1--;} cout << a; return 0; } if (calc(perm)==k) answer = (answer+1)%p; while ( next_permutation(perm.begin(), perm.end()) ) { //show(0,perm); if (calc(perm)==k) answer = (answer+1)%p; } cout << answer; /* int n=10; int nmax = n+1; for (; n < nmax ; n++) { const int kmax = (n+1)/2; vector<int> Tnk(kmax+1); vector<int> Tms(kmax+1); vector<int> perm(n); for(int i=0 ; i < n ; i++) perm[i]=i+1; int pks = peaks(perm); Tnk[pks]++; show(pks,perm); Tms[1]++; cout << 1 << endl; while ( next_permutation(perm.begin(), perm.end()) ) { pks = peaks(perm); //show(pks,perm); //if (pks==3) show(pks,perm); Tnk[pks]++; vector<int> p = perm; int m=0; while (p.size()>1) { p=reduce(p); m++; } Tms[m]++; //cout << m << endl; } for (int i=1; i < Tnk.size(); i++) cout << Tnk[i] << ", " ; cout << endl; for (int i=1; i < Tms.size(); i++) cout << Tms[i] << ", " ; cout << endl; } */ } |