SRM477 Div2 Hard(1000) CarelessSecretary
vector<int> letter; for ( int i=0; i<N; i++ ) letter.push_back( i ); int c = 0; do { int w = 0; for ( int i=0; i<K; i++ ) if ( letter[i] != i ) w++; if ( w == K ) c++; } while ( next_permutation( letter.begin(), letter.end() ) ); return c;
で、一般項を求めて、数列大辞典に訊いたら、N!のK階差分と出てきた。真面目にビットDPでも解けるらしい。
#include <iostream> #include <vector> #include <algorithm> using namespace std; class CarelessSecretary { public: int howMany( int N, int K ); }; int CarelessSecretary::howMany( int N, int K ) { const long long M = 1000000007; vector<long long> a(N+1); a[0] = 1; for ( int i=1; i<=N; i++ ) a[i] = a[i-1] * i % M; for ( int i=0; i<K; i++ ) { for ( int j=N; j>0; j-- ) a[j] = ( a[j] - a[j-1] + M ) % M; a[0] = 0; } return (int)a[N]; }