序列问题

题目描述

小 H 是个善于思考的学生, 她正在思考一个有关序列的问题. 她的面前浮现出了一个长度为 n 的序列 {ai}, 她想找出两个非空的集合 S、T. 这两个集合要满足以下的条件: 1. 两个集合中的元素都为整数, 且都在 [1, n] 里, 即 Si, Ti ∈ [1, n]. 2. 对于集合 S 中任意一个元素 x, 集合 T 中任意一个元素 y, 满足 x < y. 3. 对于大小分别为 p, q 的集合 S 与 T, 满足 a [s1] xor a [s2] xor a [s3]. ...... xor a [sp]=a [t1] and a [t2] and a [t3]. ...... and a [tq]. 小 H 想知道一共有多少对这样的集合 (S, T), 你能帮助她吗?

输入格式

第一行, 一个整数 n

第二行, n 个整数, 代表 ai.

输出格式

仅一行, 表示最后的答案.

样例输入

41
2 3 3

样例输出

4

样例解释

$S={1, 2}, T={3}, 1 xor 2=3=3 $

$S={1, 2}, T={4}, 1 xor 2=3=3 $

$S={1, 2}, T={3, 4} 1 xor 2=3 and 3=3 $

$S={3}, T={4} 3=3=3 $

数据范围

30%:\(1 \leq n \leq 10\)

60%:\(1 \leq n \leq 100\)

100%:\(1 \leq n \leq 1000\),\(0 \leq ai \lt 1024\)

Explanation

简单 DP, 需要标记这个点在这个位置有没有被选中.

Source Code

没有写高精度的 50 分 C++代码:


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 1024;

int n, arr[maxn];
lli dps[maxn][maxm][2],
    dpt[maxn][maxm];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Dynamic programming (s[i], t[i])
    dps[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 1024; j++) {
            lli tmp = dps[i - 1][j][0] + dps[i - 1][j][1];
            dps[i][j][0] = dps[i][j][0] + tmp;
            dps[i][j ^ arr[i]][1] = dps[i][j ^ arr[i]][1] + tmp;
        }
    }
    for (int i = n; i >= 1; i--) {
        dpt[i][arr[i]] = 1;
        for (int j = 0; j < 1024; j++) {
            dpt[i][j] = dpt[i][j] + dpt[i + 1][j];
            dpt[i][j & arr[i]] = dpt[i][j & arr[i]] + dpt[i + 1][j];
        }
    }
    // Processing data...
    lli res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 1024; j++)
            res = res + dps[i][j][1] * dpt[i + 1][j];
    }
    cout << res << endl;
    return 0;
}

然后用 Python 自带高精开了挂, TLE 的做法:


maxn = 1010
maxm = 1024

n = 0
arr = [0]
dps = [[[0, 0] for _2 in range(maxm)] for _1 in range(0, maxn)]
dpt = [[0 for _2 in range(maxm)] for _1 in range(0, maxn)]

n = int(input())
arr = [0] + [int(i) for i in input().split()]

# Dynamic programming (s[i], t[i])
for i in range(1, n + 1):
    dps[i][arr[i]][1] += 1
    for j in range(maxm):
        tmp = dps[i - 1][j][0] + dps[i - 1][j][1];
        dps[i][j][0] += tmp
        dps[i][j ^ arr[i]][1] += tmp

for i in range(n, -1, -1):
    dpt[i][arr[i]] = 1
    for j in range(maxm):
        tmp = dpt[i + 1][j]
        dpt[i][j] += tmp
        dpt[i][j & arr[i]] += tmp

# Processing data...
res = 0;
for i in range(1, n):
    for j in range(maxm):
        res += dps[i][j][1] * dpt[i + 1][j]

print(res)