Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- class CarelessSecretary {
- private:
- int dp[10010][14];
- int N, K;
- int solve(int mask, int picked) {
- int letters = __builtin_popcount(mask);
- if (K+picked-letters > N) return 0;
- if (dp[mask][picked] != -1) return dp[mask][picked];
- long long ans = 0;
- if (picked == K) return 1;
- ans += ((N-K-(picked-letters))*1LL*solve(mask, picked+1))%1000000007;
- ans %= 1000000007;
- for (int i = 1; i < (1 << K); i<<=1) {
- if ((i & mask) == 0) {
- if (picked) if ((1<<(picked)) == i) continue;
- ans += solve(mask^i, picked+1)%10000000007;
- ans %= 1000000007;
- }
- }
- return dp[mask][picked] = ans % 1000000007;
- }
- public:
- int howMany(int, int);
- };
- int CarelessSecretary::howMany(int _N, int _K) {
- N=_N;
- K=_K;
- memset(dp, -1, sizeof dp);
- return solve(0,0);
- }
- <%:testing-code%>
- //Powered by [KawigiEdit] 2.0!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement