test/aoj0422.test.cpp

View this file on GitHub
Last update: 2021-06-21 15:24:20+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0422

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0422"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../util/makev.cpp"

#include "../util/modint_arbitrary.cpp"
int main() {
    int n, k, m;
    cin >> n >> k >> m;
    mint::set_mod(m);
    vector<int> a(2*k-1);
    for (int i = 0; i < 2*k-1; ++i) {
        a[i] = i-k+1;
    }
    auto dp = make_v(k, 1 << a.size(), mint(0));
    for (int i = 0; i < k; ++i) {
        dp[i][0] = 1;
    }
    mint ans = mint(k).pow(n);
    for (int S = 0; S < (1 << a.size()); ++S) {
        for (int i = 0; i < a.size(); ++i) {
            if(S & (1 << i)){
                for (int j = 0; j < k; ++j) {
                    if(0 <= j+a[i] && j+a[i] < k) dp[j+a[i]][S] += dp[j][S^(1<<i)];
                }
            }
        }
        if(__builtin_popcount(S) == n-1) {
            for (int i = 0; i < k; ++i) ans -= dp[i][S];
        }
    }
    cout << ans.val << "\n";
    return 0;
}

#line 1 "test/aoj0422.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0422"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "util/makev.cpp"
template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }

/**
 * @brief make_v, chmin, chmax
 * @docs _md/makev.md
 */
#line 21 "test/aoj0422.test.cpp"

#line 1 "util/modint_arbitrary.cpp"
class modint {
    static uint &mod() { static uint mod_ = 0; return mod_; }
public:
    uint val;
    modint(const uint x = 0) : val(x % M()) {}
    uint &value() noexcept { return val; }
    const uint &value() const noexcept { return val; }
    modint operator+(const modint b) const { return modint(*this) += b; }
    modint operator-(const modint b) const { return modint(*this) -= b; }
    modint operator*(const modint b) const { return modint(*this) *= b; }
    modint operator/(const modint b) const { return modint(*this) /= b; }
    modint &operator+=(const modint b) { val += b.val; if (val >= M()) val -= M(); return *this; }
    modint &operator-=(const modint b) { if (val < b.val) val += M(); val -= b.val; return *this; }
    modint &operator*=(const modint b) { val = (ull)val * b.val % M(); return *this; }
    modint pow(ll n) const { modint x = *this, r = 1; while(n){ if(n&1) r *= x; x *= x; n >>= 1; } return r; }
    modint &operator/=(modint b) { return *this *= b.pow(M()-2); }
    static void set_mod(const uint x) { mod() = x; }
    static int M() { return mod(); }
};
using mint = modint;
#line 23 "test/aoj0422.test.cpp"
int main() {
    int n, k, m;
    cin >> n >> k >> m;
    mint::set_mod(m);
    vector<int> a(2*k-1);
    for (int i = 0; i < 2*k-1; ++i) {
        a[i] = i-k+1;
    }
    auto dp = make_v(k, 1 << a.size(), mint(0));
    for (int i = 0; i < k; ++i) {
        dp[i][0] = 1;
    }
    mint ans = mint(k).pow(n);
    for (int S = 0; S < (1 << a.size()); ++S) {
        for (int i = 0; i < a.size(); ++i) {
            if(S & (1 << i)){
                for (int j = 0; j < k; ++j) {
                    if(0 <= j+a[i] && j+a[i] < k) dp[j+a[i]][S] += dp[j][S^(1<<i)];
                }
            }
        }
        if(__builtin_popcount(S) == n-1) {
            for (int i = 0; i < k; ++i) ans -= dp[i][S];
        }
    }
    cout << ans.val << "\n";
    return 0;
}