Advertisement
Guest User

Untitled

a guest
May 13th, 2018
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair <int, int> ii;
  6.  
  7. const int Maxn = 10;
  8. const int Maxd = 11;
  9. const int mod = 1000000007;
  10.  
  11. int a, b, c;
  12. vector <ll> un;
  13. vector <ii> V[Maxn][Maxd];
  14. ll ways[200005];
  15. int A[Maxn][Maxn];
  16.  
  17. void Gen(int lvl, int from, ll cur)
  18. {
  19.     if (lvl >= b) un.push_back(cur);
  20.     else {
  21.         for (int i = from; i >= 0; i--)
  22.             Gen(lvl + 1, i, Maxd * cur + i);
  23.     }
  24. }
  25.  
  26. int main()
  27. {
  28.     scanf("%d %d %d", &a, &b, &c);
  29.     Gen(0, c, 0);
  30.     sort(un.begin(), un.end());
  31.     for (int i = 0; i < un.size(); i++) {
  32.         ll num = un[i];
  33.         ll pw = 1;
  34.         for (int j = 0; j < b; j++) {
  35.             int dig = num % Maxd; num /= Maxd;
  36.             if (dig > 0) {
  37.                 int ind = lower_bound(un.begin(), un.end(), un[i] - pw) - un.begin();
  38.                 if (ind < un.size() && un[ind] == un[i] - pw)
  39.                     V[j][dig].push_back(ii(i, ind));
  40.             }
  41.             pw *= Maxd;
  42.         }
  43.         ways[i] = 1;
  44.     }
  45.     for (int i = 0; i < a; i++)
  46.         for (int j = 0; j < b; j++)
  47.             scanf("%d", &A[i][j]);
  48.     for (int i = 0; i < a; i++) {
  49.         for (int j = 0; j < un.size(); j++) {
  50.             ll num = un[j];
  51.             bool ok = true;
  52.             for (int l = 0; l < b && ok; l++) {
  53.                 int dig = num % Maxd; num /= Maxd;
  54.                 ok = dig >= A[i][b - 1 - l];
  55.             }
  56.             if (!ok) ways[j] = 0;
  57.         }
  58.         if (i + 1 < a) {
  59.             for (int j = 0; j < b; j++)
  60.                 for (int d = c; d > 0; d--)
  61.                     for (int l = 0; l < V[j][d].size(); l++) {
  62.                         ii p = V[j][d][l];
  63.                         ways[p.second] = (ways[p.second] + ways[p.first]) % mod;
  64.                     }  
  65.         }
  66.     }
  67.     int res = 0;
  68.     for (int i = 0; i < un.size(); i++)
  69.         res = (res + ways[i]) % mod;
  70.     printf("%d\n", res);
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement