题解：P1329 数列

ELECTRODE_kaf · 2025-02-08 21:04:21 · 题解

设 dp_{i,j} 表示 \sum_{k=1}^i a_k=j 的方案数。转移是平凡的，与背包问题类似。

暴力的做法：假设所有数都是前一个数加一，即构造 a_i=i-1，总和就是 n(n-1)/2。将 a_i 减 2 会使所有数总和减少 2(n-i+1)，所以目标就是用不同的 (n-i+1) 凑出 goal=s-n(n-1)/2。这么做时间复杂度是 O(2^n) 的，但可以用来输出方案（所以就出现了一道题正解中同时使用正解和暴力做法的情况）。

const ll N = 2000, S = 6000;
const lll mod = (lll)(1) << 64;
lll dp[N][S];
ll n, s, goal, cnt, ch[N];

void dfs(ll p, ll cur) {
    if (cur > goal)
        return;
    elif(p > n) {
        if (cur == goal) {
            cnt++;
            ll sum = 0;

            rep(i, 1, n) {
                sum += ch[i];
                cout << sum << ' ';
            }

            endl;

            if (cnt >= 100)
                exit(0);
        }
    } else {
        ch[p] = -1;
        dfs(p + 1, cur + (n - p + 1));
        ch[p] = 1;
        dfs(p + 1, cur);
    }
}

int main() {
    cin >> n >> s;

    if (abs(s) > n * (n - 1) / 2 or (n * (n - 1) / 2 - s) % 2) {
        cout << 0;
        return 0;
    }

    goal = (n * (n - 1) / 2 - s) / 2;
    dp[1][0] = 1;

    rep(i, 2, n) {
        ll dis = n - i + 1;
        cpy(dp[i], dp[i - 1]);

        rep(j, dis, S - 1) (dp[i][j] += dp[i - 1][j - dis]) %= mod;
    }

    cout << (ull)(dp[n][goal]) << '\n';
    dfs(2, 0);
}

代码宏定义在我个人空间自取。