SHARE
TWEET

Untitled

a guest Sep 25th, 2016 172 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <set>
  9. #include <map>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <functional>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <valarray>
  16. #include <complex>
  17. #include <queue>
  18. #include <cassert>
  19. #include <bitset>
  20. using namespace std;
  21.  
  22. #ifdef LOCAL
  23.     #define debug_flag 1
  24. #else
  25.     #define debug_flag 0
  26. #endif
  27.  
  28. template <class T1, class T2 >
  29. std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
  30. {
  31.     os << "[" << p.first << ", " << p.second << "]";
  32.     return os;
  33. }
  34.  
  35. template <class T >
  36. std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
  37. {
  38.     os << "[";
  39.     bool first = true;
  40.     for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
  41.     {
  42.         if (!first)
  43.             os << ", ";
  44.         first = false;
  45.         os << *it;
  46.     }
  47.     os << "]";
  48.     return os;
  49. }
  50.  
  51. #define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }
  52.  
  53. vector<string> _split(const string& s, char c) {
  54.     vector<string> v;
  55.     stringstream ss(s);
  56.     string x;
  57.     while (getline(ss, x, c))
  58.         v.emplace_back(x);
  59.     return v;
  60. }
  61.  
  62. void _print(vector<string>::iterator) {}
  63. template<typename T, typename... Args>
  64. void _print(vector<string>::iterator it, T a, Args... args) {
  65.     string name = it -> substr((*it)[0] == ' ', it -> length());
  66.     if (isalpha(name[0]))
  67.         cerr << name  << " = " << a << " ";
  68.     else
  69.         cerr << name << " ";
  70.     _print(++it, args...);
  71. }
  72.  
  73. typedef long long int int64;
  74.  
  75. const int bs = 1000000007;
  76.  
  77. const int N = 105;
  78. const int K = 10;
  79. const int M = 31;
  80.  
  81. int n,m,k;
  82. int D[N];
  83. int dp[N][1<<K][M];
  84. int precalc[1<<K];
  85.  
  86. void add(int&a,int b)
  87. {
  88.     a+=b;
  89.     if (a>=bs)
  90.         a-=bs;
  91. }
  92.  
  93. int main()
  94. {
  95. #ifdef LOCAL
  96.     freopen ("input.txt", "r", stdin);
  97. #endif
  98.  
  99.     cin>>n>>m>>k;
  100.     for (int i=1;i<n;i++)
  101.     {
  102.         cin>>D[i];
  103.     }
  104.  
  105.     for (int mask=0;mask<(1<<k);mask++)
  106.     {
  107.         int crosses=0;
  108.  
  109.         for (int i=0;i+1<k;i++)
  110.         {
  111.             int v1=(mask&(1<<i));
  112.             int v2=(mask&(1<<(i+1)));
  113.             if (v1>1)
  114.                 v1=1;
  115.             if (v2>1)
  116.                 v2=1;
  117.             if (v1!=v2)
  118.                 crosses++;
  119.         }
  120.         precalc[mask]=crosses;
  121.     }
  122.  
  123.     for (int mask=0;mask<(1<<k);mask++)
  124.     {
  125.     //  dbg(mask,precalc[mask]);
  126.     }
  127.  
  128.     dp[0][0][0]=1;
  129.     for (int i=0;i<n;i++)
  130.     {
  131.         for (int mask=0;mask<(1<<k);mask++)
  132.         {
  133.             for (int rem=0;rem<m;rem++)
  134.             {
  135.                 if (dp[i][mask][rem])
  136.                 {
  137.                 //  dbg(i,mask,rem,dp[i][mask][rem]);
  138.                 }
  139.                 int new_rem=rem;
  140.                 new_rem+=precalc[mask]*D[i];
  141.                 new_rem%=m;
  142.                 // don't take
  143.                 add(dp[i+1][mask][new_rem],dp[i][mask][rem]);
  144.                 // take at x
  145.                 for (int x=0;x<k;x++)
  146.                 {
  147.                     if (!(mask&(1<<x)))
  148.                     {
  149.                         add(dp[i+1][mask|(1<<x)][new_rem],dp[i][mask][rem]);
  150.                     }
  151.                 }
  152.             }
  153.         }
  154.     }
  155.  
  156.     cout<<dp[n][(1<<k)-1][0]<<endl;
  157.  
  158.     return 0;
  159. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top