马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
标题配景
NOIP2015 遍及组 T3、深入浅出进阶1-5
标题形貌
一条狭长的纸带被匀称分别出了 nnn 个格子，格子编号从 111 到 nnn。每个格子上都染了一种颜色 coloricolor_icolori 用 [1,m][1,m][1,m] 当中的一个整数表现），而且写了一个数字 numberinumber_inumberi。
编号123456颜色和数字5\color{blue}{5}55\color{blue}{5}53\color{red}{3}32\color{red}{2}22\color{blue}{2}22\color{red}{2}2界说一种特殊的三元组：(x,y,z)(x,y,z)(x,y,z)，此中 x,y,zx,y,zx,y,z 都代表纸带上格子的编号，这里的三元组要求满意以下两个条件：
- x,y,zx,y,zx,y,z 都是整数，x<y<z,y−x=z−yx<y<z,y-x=z-yx<y<z,y−x=z−y。
- colorx=colorzcolor_x=color_zcolorx=colorz。
满意上述条件的三元组的分数规定为 (x+z)×(numberx+numberz)(x+z) \times (number_x+number_z)(x+z)×(numberx+numberz)。整个纸带的分数规定为全部满意条件的三元组的分数的和。这个分数大概会很大，你只要输出整个纸带的分数除以 100071000710007 所得的余数即可。
思绪：
标题等价于求对于全部满意 x≡z( mod 2)，colorx=colorzx \equiv z(\bmod 2)，color_x = color_zx≡z(mod2)，colorx=colorz 的二元组 (x,z)(x,z)(x,z) 中 (x+z)×(numberx+numberz)(x+z) \times (number_x+number_z)(x+z)×(numberx+numberz) 数值。轻易想到将标题全部输入按照差异颜色和奇数偶数举行处置惩罚。
不妨让题目特殊化：假设我们当前要处置惩罚 333 个雷同颜色，编号和数字依次为：
编号159数字a1a_1a1a5a_5a5a9a_9a9有答案
ans=(1+5)(a1+a5)+(1+9)(a1+a9)+(5+9)(a5+a9)=(2×1+5+9)a1+(2×5+1+9)a5+(2×9+1+5)a9ans = (1+5)(a_1 + a_5)+(1+9)(a_1+a_9)+(5+9)(a_5+a_9)= (2\times1+5+9)a_1 +(2\times 5+1+9)a_5+(2\times9+1+5)a_9ans=(1+5)(a1+a5)+(1+9)(a1+a9)+(5+9)(a5+a9)=(2×1+5+9)a1+(2×5+1+9)a5+(2×9+1+5)a9
进一步的，上述式子便是 (1+5+9)(a1+a5+a9)+(1×a1+5×a5+9×a9)(1+5+9)(a_1+a_5+a_9)+(1\times a_1 +5 \times a_5 + 9 \times a_9)(1+5+9)(a1+a5+a9)+(1×a1+5×a5+9×a9)
一样平常化题目，假设处置惩罚 mmm 个同色且都为奇数（偶数）的数字，编号和数字依次为
编号：x1,x2…xmx_1,x_2 \dots x_mx1,x2…xm
数字：a1,a2…ama_1,a_2 \dots a_ma1,a2…am
有 ans=(a1+a2)(x1+x2)+(a1+a3)(x1+x3)⋯=a1(x1+x2+x1+x3⋯+x1+xm)+a2⋯+am(… )ans = (a_1 + a_2)(x_1+x_2) + (a_1+a_3)(x_1+x_3)\dots=a1(x_1+x_2+x_1+x_3\dots+x_1+x_m)+a2 \dots+a_m(\dots )ans=(a1+a2)(x1+x2)+(a1+a3)(x1+x3)⋯=a1(x1+x2+x1+x3⋯+x1+xm)+a2⋯+am(…)
化简，有 ans=a1[(m−1)x1+∑i=2mxi]+a2[(m−1)x2+∑i=1mxi−x2]⋯=a1[(m−2)x1+∑i=1mxi]+a2⋯=(a1+a2+a3…am)∑i=1mxi+(m−2)∑i=1m(aixi)ans = a_1[(m-1)x_1+\sum_{i=2}^{m}{x_i}]+a_2[(m-1)x_2+\sum_{i=1}^{m}{x_i} - x_2]\dots=a_1[(m-2)x_1+\sum_{i=1}^{m}{x_i}]+a_2\dots=(a_1+a_2+a_3\dots a_m)\sum_{i=1}^{m}{x_i} + (m-2)\sum_{i=1}^{m}{(a_ix_i)}ans=a1[(m−1)x1+∑i=2mxi]+a2[(m−1)x2+∑i=1mxi−x2]⋯=a1[(m−2)x1+∑i=1mxi]+a2⋯=(a1+a2+a3…am)∑i=1mxi+(m−2)∑i=1m(aixi)
终极，可得到以下式子：
ans=∑i=1mai×∑j=1mxi+(m−2)×∑k=1m(akxk)ans = \sum_{i=1}^{m}{a_i} \times \sum_{j=1}^{m}{x_i}+(m-2) \times \sum_{k=1}^{m}{(a_kx_k)}ans=∑i=1mai×∑j=1mxi+(m−2)×∑k=1m(akxk)
注意到以上全部式子都能在输入时处置惩罚，故本题办理，算法时间复杂度 O(n+m)O(n+m)O(n+m)
代码
- #include<bits/stdc++.h>
- #define int long long
- const int p = 10007;
- using namespace std;
- int n,m;
- int num[100005],c[100005];
- int s[100005][2],s2[100005][2],s3[100005][2];
- int ans = 0;
- signed main() {
- scanf("%lld %lld",&n,&m);
- for(int i = 1;i <= n;i++) scanf("%lld",&num[i]);
- for(int i = 1;i <= n;i++) scanf("%lld",&c[i]),s3[c[i]][i % 2]++;//统计这一类的数字数量
- for(int i = 1;i <= n;i++) {
- s[c[i]][i % 2] += i;//统计x数列的总和
- s2[c[i]][i % 2] += num[i];//统计a数列总和
- if(s3[c[i]][i % 2] >= 2)ans += (s3[c[i]][i % 2] - 2) * num[i] * i;//加上所求式子后面的那一部分
- ans %= p;
- }
- for(int i = 1;i <= m;i++) {
- for(int j = 0;j <= 1;j++) {
- if(s3[i][j] <= 1) continue;
- ans += s[i][j] * s2[i][j];//加上所求式子前面的那一部分
- ans %= p;
- }
- }
- printf("%lld\n",ans);
- return 0;
- }
|
发表于 2025-12-3 00:42:14