Yukicoder No.287 場合の数

埋め込みを思わせる制約であるが、普通にDPすれば余裕を持って間に合う。$N \le 4000$とかでもよかったのではないか。

solution

DP。変数の個数$L = 8$に対し$O(LN^2)$。

既に決定した変数の個数$i$とその総和$j$からそのようなものの個数$\mathrm{dp}_{i,j}$とすればよい。

implementation

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
const int l = 8;
int main() {
    int n; scanf("%d", &n);
    vector<vector<ll> > dp = vectors<ll>(0, l+1, 6*n+1);
    dp[0][0] = 1;
    repeat (i,l) {
        repeat (j,6*n+1) {
            repeat (k,n+1) if (j+k < 6*n+1) {
                dp[i+1][j+k] += dp[i][j];
            }
        }
    }
    printf("%lld\n", dp[l][6*n]);
    return 0;
}