CometOJ_#7_C

· · 个人记录

CometOJ_#7_C

题目连接

题目描述就不放了。

其实和一道以前做过的题目很像，代码就只多了一个 cnt 。

写这篇的主要目的还是反省。

对以前的题目的一些特殊的方法要总结下来写在一篇文章里，并且加上题目。

感觉以前有好多东西都落下了。。。

从现在开始一点点补上好了。

比如说这道题：

对于两个点之间与下标有关的（一次）贡献，可以转换为 已经放了的数与还没放的数之 间都有 1 的贡献。

其实高次也可以，但是每个数之间要分开来维护，因为：

(a + 1) ^ 2 = a ^ 2 + 2 \cdot a + 1

很显然，还要维护 1 次的值。

而且每对数的贡献只与自身有关。

看完后就比较明显了（？！！），因为对所有的情况来说都有这样的贡献，所以还要维护 这种状态下的情况数。

简短的代码


int main() {
    rep (S, 1, 65535) Cnt[S] = Cnt[S >> 1] + (S & 1);
    rep (ks, 1, read<int>()) {
        n = read<int>(), uplim = (1 << n) - 1;
        rep (i, 1, n) p[i] = read<int>();

        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        g[0] = 1; // g 存的是方案数

        rep (i, 0, n - 1) {
            rep (S, 0, uplim) if (Cnt[S] == i && g[S]) {
                int T = uplim ^ S, w = 0, cnt = 0;
                rep (j, 0, n - 1) {
                    if ((1 << j) & T) w += j + 1, ++cnt;
                    else f[S] += g[S] * (cnt * (j + 1) - w);
                }
                rep (j, 0, n - 1) if (((1 << j) & T) && p[j + 1] != i + 1) {
                    if (f[S | (1 << j)] == -1) f[S | (1 << j)] = 0;
                    f[S | (1 << j)] += f[S], g[S | (1 << j)] += g[S];
                }
            }
        }

        cout << (f[uplim] != -1 ? f[uplim] : 0) << endl;
    }
    return 0;
}