SRM477 Div2 Hard(1000) CarelessSecretary

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];
}