长兴县建设管理网站,wordpress健身预定主题,网络营销模式,智能管理系统软件题目背景
NOIP2015 普及组 T3、深入浅出进阶1-5
题目描述
一条狭长的纸带被均匀划分出了 n n n 个格子#xff0c;格子编号从 1 1 1 到 n n n。每个格子上都染了一种颜色 c o l o r i color_i colori 用 [ 1 , m ] [1,m] [1,m] 当中的一个整数表示#xff09;…题目背景
NOIP2015 普及组 T3、深入浅出进阶1-5
题目描述
一条狭长的纸带被均匀划分出了 n n n 个格子格子编号从 1 1 1 到 n n n。每个格子上都染了一种颜色 c o l o r i color_i colori 用 [ 1 , m ] [1,m] [1,m] 当中的一个整数表示并且写了一个数字 n u m b e r i number_i numberi。
编号123456颜色和数字 5 \color{blue}{5} 5 5 \color{blue}{5} 5 3 \color{red}{3} 3 2 \color{red}{2} 2 2 \color{blue}{2} 2 2 \color{red}{2} 2
定义一种特殊的三元组 ( x , y , z ) (x,y,z) (x,y,z)其中 x , y , z x,y,z x,y,z 都代表纸带上格子的编号这里的三元组要求满足以下两个条件 x , y , z x,y,z x,y,z 都是整数 x y z , y − x z − y xyz,y-xz-y xyz,y−xz−y。 c o l o r x c o l o r z color_xcolor_z colorxcolorz。
满足上述条件的三元组的分数规定为 ( x z ) × ( n u m b e r x n u m b e r z ) (xz) \times (number_xnumber_z) (xz)×(numberxnumberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大你只要输出整个纸带的分数除以 10007 10007 10007 所得的余数即可。
思路
题目等价于求对于所有满足 x ≡ z ( m o d 2 ) c o l o r x c o l o r z x \equiv z(\bmod 2)color_x color_z x≡z(mod2)colorxcolorz 的二元组 ( x , z ) (x,z) (x,z) 中 ( x z ) × ( n u m b e r x n u m b e r z ) (xz) \times (number_xnumber_z) (xz)×(numberxnumberz) 数值。容易想到将题目所有输入按照不同颜色和奇数偶数进行处理。
不妨让问题特殊化假设我们当前要处理 3 3 3 个相同颜色编号和数字依次为
编号159数字 a 1 a_1 a1 a 5 a_5 a5 a 9 a_9 a9
有答案 a n s ( 1 5 ) ( a 1 a 5 ) ( 1 9 ) ( a 1 a 9 ) ( 5 9 ) ( a 5 a 9 ) ( 2 × 1 5 9 ) a 1 ( 2 × 5 1 9 ) a 5 ( 2 × 9 1 5 ) a 9 ans (15)(a_1 a_5)(19)(a_1a_9)(59)(a_5a_9) (2\times159)a_1 (2\times 519)a_5(2\times915)a_9 ans(15)(a1a5)(19)(a1a9)(59)(a5a9)(2×159)a1(2×519)a5(2×915)a9
进一步的上述式子等于 ( 1 5 9 ) ( a 1 a 5 a 9 ) ( 1 × a 1 5 × a 5 9 × a 9 ) (159)(a_1a_5a_9)(1\times a_1 5 \times a_5 9 \times a_9) (159)(a1a5a9)(1×a15×a59×a9)
一般化问题假设处理 m m m 个同色且都为奇数偶数的数字编号和数字依次为
编号 x 1 , x 2 … x m x_1,x_2 \dots x_m x1,x2…xm
数字 a 1 , a 2 … a m a_1,a_2 \dots a_m a1,a2…am
有 a n s ( a 1 a 2 ) ( x 1 x 2 ) ( a 1 a 3 ) ( x 1 x 3 ) ⋯ a 1 ( x 1 x 2 x 1 x 3 ⋯ x 1 x m ) a 2 ⋯ a m ( … ) ans (a_1 a_2)(x_1x_2) (a_1a_3)(x_1x_3)\dotsa1(x_1x_2x_1x_3\dotsx_1x_m)a2 \dotsa_m(\dots ) ans(a1a2)(x1x2)(a1a3)(x1x3)⋯a1(x1x2x1x3⋯x1xm)a2⋯am(…)
化简有 a n s a 1 [ ( m − 1 ) x 1 ∑ i 2 m x i ] a 2 [ ( m − 1 ) x 2 ∑ i 1 m x i − x 2 ] ⋯ a 1 [ ( m − 2 ) x 1 ∑ i 1 m x i ] a 2 ⋯ ( a 1 a 2 a 3 … a m ) ∑ i 1 m x i ( m − 2 ) ∑ i 1 m ( a i x i ) ans a_1[(m-1)x_1\sum_{i2}^{m}{x_i}]a_2[(m-1)x_2\sum_{i1}^{m}{x_i} - x_2]\dotsa_1[(m-2)x_1\sum_{i1}^{m}{x_i}]a_2\dots(a_1a_2a_3\dots a_m)\sum_{i1}^{m}{x_i} (m-2)\sum_{i1}^{m}{(a_ix_i)} ansa1[(m−1)x1∑i2mxi]a2[(m−1)x2∑i1mxi−x2]⋯a1[(m−2)x1∑i1mxi]a2⋯(a1a2a3…am)∑i1mxi(m−2)∑i1m(aixi)
最终可得到以下式子 a n s ∑ i 1 m a i × ∑ j 1 m x i ( m − 2 ) × ∑ k 1 m ( a k x k ) ans \sum_{i1}^{m}{a_i} \times \sum_{j1}^{m}{x_i}(m-2) \times \sum_{k1}^{m}{(a_kx_k)} ans∑i1mai×∑j1mxi(m−2)×∑k1m(akxk)
注意到以上所有式子都能在输入时处理故本题解决算法时间复杂度 O ( n m ) O(nm) O(nm)
代码
#includebits/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;
}
