1525

kexin0909

1525题解
本题解不贴代码，较适用于周日上午提高组学拓扑排序的同学。
两种骗分方法
1.枚举xyz,看是否形成三元组，形成就加入和。
3.不难只要xz奇偶性相同，y就存在且一定，枚举xz即可。
正解
如果要不时间超限，就要优化至O(n)的时间复杂度。奇偶思路保留
先明确，此题无后效性
有点儿dp，但不够最值。（本身不是dp，只是用dp的讲法）
以下我用dp讲
状态
新加一个量只会作为z影响同一与同色同奇偶其它数x发生影响。
(x+z)*(number[x]+number[z])
=x*number[x]+x*number[z]+z*number[x]+z*number[z]
c表颜色，oe表奇偶
以下均为同色同奇偶
n[c][oe]:所有x*number[x]的和
q[c][oe]:所有x的和
n[c][oe]:所有number[x]的和
ans:答案
状态转移
ans = (ans + ((nq[c][oe] % MOD) + ((n[c][oe] % MOD) * (number % MOD)) % MOD + ((i % MOD) *
(q[c][oe] % MOD)) % MOD + ((i % MOD) * (number % MOD) * (cnt[c][oe] % MOD)) % MOD) % MOD) % MOD;
cnt[c][oe]++;
n[c][oe] = (n[c][oe] + i) % MOD;
q[c][oe] = (q[c][oe] + number) % MOD;
nq[c][oe] = ((nq[c][oe] % MOD) + (((i % MOD) * (number % MOD)) % MOD)) % MOD;
i即为z
注意:由于x<z,ans必须最先转移
不开long long 见祖宗

liushupeng

楼主楼主，有没有更简便，更有效的方法？？？（不喜欢dp。。。）

kexin0909

本来也不是dp

kexin0909

做好卡常，能骗高分

kexin0909

#include <bits/stdc++.h>
using namespace std;
#define MAXM 100000
#define MAXN 100000
#define MOD 10007
#define int long long
int cnt[MAXM + 5][3];
int number[MAXN], color[MAXN];
int nq[MAXM + 5][3], n[MAXM + 5][3], q[MAXM + 5][3];
signed main() {
        int n1, m;
        cin >> n1 >> m;
        for (int i = 1; i <= n1; i++) {
                cin >> number[i];
                number[i] %= MOD;
        }
        for (int i = 1; i <= n1; i++) {
                cin >> color[i];
        }
        int ans = 0;
        for (int i = 1; i <= n1; i++) {
                int oe = i % 2 + 1; //奇2偶1
                int c = color[i];
                ans = (ans + ((nq[c][oe] % MOD) + ((n[c][oe] % MOD) * (number[i] % MOD)) % MOD + ((i % MOD) *
                              (q[c][oe] % MOD)) % MOD + ((i % MOD) * (number[i] % MOD) * (cnt[c][oe] % MOD)) % MOD) % MOD) % MOD;
                cnt[c][oe]++;
                n[c][oe] = (n[c][oe] + i) % MOD;
                q[c][oe] = (q[c][oe] + number[i]) % MOD;
                nq[c][oe] = ((nq[c][oe] % MOD) + (((i % MOD) * (number[i] % MOD)) % MOD)) % MOD;
        }
        cout << ans % MOD;
        return 0;
}