Submission #6384104


Source Code Expand

Copy
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define int long long
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
  bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }

int Solve1(int n, int k, int m) { // nie ma k + 1 kolejnych
  VVI dp(n + 2, VI(n + 2));
  dp[0][0] = 1;
  RE (i, n) {
    REP (prv, k + 1) {
      dp[i][0] = (dp[i][0] + dp[i - 1][prv]) % m;
      if (prv < k) {
        dp[i][prv + 1] = (dp[i][prv + 1] + dp[i - 1][prv]) % m;
      }
    }
  }
  int res = 0;
  REP (prv, k + 1) {
    res = (res + dp[n][prv]) % m;
  }
  return res;
}

const int N = 80;
int dp[2 * N][N][N][N];
int32_t main() {

  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  cerr << fixed << setprecision(10);
  cin.tie(0);
  //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  
  int n, k, m;
  cin>>n>>k>>m;
  if (k % 2 == 0) {
    cout<<Solve1(n / 2, k / 2, m) * Solve1(n - n / 2, k / 2, m) % m<<endl;
    return 0;
  }
  if (k == 1) {
    cout<<Solve1(n, 2, m)<<endl;
    return 0;
  }
  dp[0][0][0][N - 1] = 1;
  // dp[a][b][c][d] 
  // pozycja a
  // na parzystosci a dlugosc b
  // na parzystosci a-1 dlugosc c
  // dluzszy z nich nie moze dojsc do dlugosci d
  RE (i, n) {
    REP (prv_b, N - 2) {
      REP (prv_c, N - 2) {
        REP (prv_d, N) {
          // dodajemy x
          int nb = prv_c + 1;
          int nc = prv_b;
          int nd = prv_d;
          if (nb > nc && nc >= 1 && nb * 2 >= k + 3) {
            mini(nd, nb + (k - 2 * nc + 1) / 2);
            maxi(nd, 0ll);
          }
          if (i >= 5 && prv_b == 2 && prv_c == 2 && prv_d == N - 1) {
            debug(nb, nc, nd);
          }
          dp[i][nb][nc][nd] = (dp[i][nb][nc][nd] + dp[i - 1][prv_b][prv_c][prv_d]) % m;
          if (i >= 5 && prv_b == 2 && prv_c == 2 && prv_d == N - 1) {
            debug(dp[i][nb][nc][nd]);
          }
          if (nb >= nd || nc >= nd) {
            if (dp[i - 1][prv_b][prv_c][prv_d]) {
              debug(i, nb, nc, nd, prv_b, prv_c, prv_d, dp[i][nb][nc][nd], dp[i - 1][prv_b][prv_c][prv_d]);
            }
            dp[i][nb][nc][nd] = 0;
          }
          if (i >= 5 && prv_b == 2 && prv_c == 2 && prv_d == N - 1) {
            debug(dp[i][nb][nc][nd]);
          }
          // dodajemy o
          nb = 0;
          nc = prv_b;
          if (prv_c >= prv_b) {
            nd = N - 1;
          }
          dp[i][nb][nc][nd] = (dp[i][nb][nc][nd] + dp[i - 1][prv_b][prv_c][prv_d]) % m;
          if (nb >= nd || nc >= nd) {
            dp[i][nb][nc][nd] = 0;
          }
        }
      }
    }
  }
  int res = 0;
  REP (prv_b, N - 1) {
    REP (prv_c, N - 1) {
      REP (prv_d, N) {
        res = (res + dp[n][prv_b][prv_c][prv_d]) % m;
      }
    }
  }
  cout<<res<<endl;
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  return 0;
}

Submission Info

Submission Time
Task E - Develop
User Swistakk
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 5609 Byte
Status AC
Exec Time 1141 ms
Memory 602368 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 5
AC × 31
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
Case Name Status Exec Time Memory
01.txt AC 1 ms 256 KB
02.txt AC 1136 ms 602368 KB
03.txt AC 1 ms 256 KB
04.txt AC 1112 ms 598272 KB
05.txt AC 1016 ms 559360 KB
06.txt AC 1004 ms 559360 KB
07.txt AC 1 ms 256 KB
08.txt AC 1 ms 256 KB
09.txt AC 1 ms 384 KB
10.txt AC 1 ms 384 KB
11.txt AC 1 ms 256 KB
12.txt AC 967 ms 514304 KB
13.txt AC 1025 ms 555264 KB
14.txt AC 1023 ms 592128 KB
15.txt AC 787 ms 454912 KB
16.txt AC 1028 ms 592128 KB
17.txt AC 1049 ms 594176 KB
18.txt AC 999 ms 559360 KB
19.txt AC 1095 ms 602368 KB
20.txt AC 1029 ms 559360 KB
21.txt AC 1098 ms 592128 KB
22.txt AC 1093 ms 583936 KB
23.txt AC 1126 ms 592128 KB
24.txt AC 1141 ms 602368 KB
25.txt AC 1 ms 256 KB
26.txt AC 1 ms 256 KB
s1.txt AC 1 ms 256 KB
s2.txt AC 50 ms 26880 KB
s3.txt AC 1 ms 256 KB
s4.txt AC 126 ms 71936 KB
s5.txt AC 902 ms 495872 KB