fork download
  1. //Author: Václav Volhejn (-Wave-)
  2. #include <iostream>
  3. #include <fstream>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <string>
  8. #include <map>
  9. using namespace std;
  10. #define rep(i,a,n) for (int i=a;i<n;i++)
  11. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  12. #define ll long long
  13.  
  14. const bool distribute = true;
  15.  
  16. ll fact(int n) {
  17. return n ? (fact(n - 1) * n) : 1;
  18. }
  19. const int MAXK = 26;
  20. map<ll, ll> m[MAXK];
  21. ll s;
  22.  
  23. int main() {
  24. istream *in = distribute ? (&cin) : (new ifstream("in.txt"));
  25. int n, k;
  26. *in >> n >> k >> s;
  27. ll input[n];
  28. rep(i, 0, n) *in >> input[i];
  29.  
  30. rep(mask, 0, pow(3, n / 2)) {
  31. int c = mask;
  32. int used = 0;
  33. bool ok = true;
  34. ll sum = 0;
  35. rep(i, 0, n / 2) {
  36. if(c % 3 == 1) sum += input[i];
  37. if(c % 3 == 2) {
  38. used++;
  39. if((used > k) || (input[i] > 18)) {
  40. ok = false;
  41. break;
  42. }
  43. sum += fact(input[i]);
  44. }
  45. c /= 3;
  46. }
  47. if(ok) {
  48. if(!m[used].count(sum))
  49. m[used][sum] = 0;
  50. m[used][sum]++;
  51. }
  52. }
  53. ll res = 0;
  54. rep(mask, 0, pow(3, n - n / 2)) {
  55. int c = mask;
  56. int used = 0;
  57. bool ok = true;
  58. ll sum = 0;
  59. rep(i, n / 2, n) {
  60. if(c % 3 == 1) sum += input[i];
  61. if(c % 3 == 2) {
  62. used++;
  63. if((used > k) || (input[i] > 18)) {
  64. ok = false;
  65. break;
  66. }
  67. sum += fact(input[i]);
  68. }
  69. c /= 3;
  70. }
  71. if(ok) {
  72. rep(i, 0, k - used + 1) {
  73. if(!m[i].count(s - sum)) continue;
  74. res += m[i][s - sum];
  75. }
  76. }
  77. }
  78. cout << res << endl;
  79. return 0;
  80. }
Success #stdin #stdout 1.14s 3280KB
stdin
25 9 137
4 3 1 4 1 2 2 1 1 1 4 4 3 4 4 3 2 1 3 2 4 2 4 1 4
stdout
2310192318