首页 > 代码库 > The Romantic Hero

The Romantic Hero

题目链接

  • 题意:
    n个数,找到两个下标i和j(i < j),在1-i中选取若干个数的异或值等于在j-n中选取若干个数的按位与值,两个集合都非空,求满足条件的集合数有多少
  • 分析:
    对于一个i,如果知道左边所有的取值情况和右边所有的取值情况,乘机就是一部分答案,那么就是DP预处理出一侧的值的情况。
    重点思考一下DP的状态表示:DP[i][j]表示以i位置数字为结尾、操作值为j的情况数,这里的情况是表示任意个数字可以组合出的和为j的情况数,如果不表示以i为结尾,那么就会出现重复。
    为什么这样DP不会出现重复呢,从两个方面来像:对于dp[x][]和dp[y][],因为这两个状态的最大值不相同,所以数列不会相同,也就是说DP所表示的状态没有重叠;对于一个序列,它的计算结果只有一种,所以只属于dp[x][]的某一个状态,也不会重复(假如一个序列可以得到多个计算结果,那么就不能这样DP了,因为一个确定的序列可以属于多个状态)。

const int MAXN = 1024;

int ipt[MAXN];
LL dp1[MAXN][MAXN], dp2[MAXN][MAXN], sum1[MAXN][MAXN], sum2[MAXN][MAXN];

int main()
{
    int T, n;
    RI(T);
    FE(kase, 1, T)
    {
        CLR(dp1, 0); CLR(sum1, 0);
        CLR(dp2, 0); CLR(sum2, 0);
        RI(n);
        REP(i, n)
            RI(ipt[i]);
        dp1[0][ipt[0]] = sum1[0][ipt[0]] = 1;
        FF(i, 1, n)
        {
            REP(j, MAXN)
                dp1[i][j ^ ipt[i]] = (sum1[i - 1][j] + dp1[i][j ^ ipt[i]]) % MOD;
            dp1[i][ipt[i]]++;
            REP(j, MAXN)
                sum1[i][j] = (sum1[i - 1][j] + dp1[i][j]) % MOD;
        }
        dp2[n - 1][ipt[n - 1]] = sum2[n - 1][ipt[n - 1]] = 1;
        FED(i, n - 2, 0)
        {
            REP(j, MAXN)
                dp2[i][j & ipt[i]] = (sum2[i + 1][j] + dp2[i][j & ipt[i]]) % MOD;
            dp2[i][ipt[i]]++;
            REP(j, MAXN)
                sum2[i][j] = (sum2[i + 1][j] + dp2[i][j]) % MOD;
        }
        LL ans = 0;
        REP(i, n - 1)
            REP(j, MAXN)
                ans = (ans + dp1[i][j] * sum2[i + 1][j]) % MOD;
        cout << ans << endl;
    }
    return 0;
}