[Luogu P2671] [noip PJ 2015 T3] solution to summation problem

This problem has a bit of mathematical flavor. Think clearly. The code is not difficult to write.

The triplet (x,y,z)(x,y,z)(x,y,z) that satisfies the condition must satisfy y − x=z − yy-x=z-yy − x=z − y, and X + Z = 2yx + Z = 2Y. Because x, y, ZX, y, Z are integers, x,zx,zx,z are parity. And because colorx=colorzcolor_x=color_zcolorx = colorz. Only x,zx,zx,z are needed to calculate the answer, so it has nothing to do with yyy in the end.

Considering colorx = colorz color_ x=color_ We can use the same number of zundercolor as zundercolor, so we can store it in the same number of zundercolor, and then we can use the same number of zundercolor.

How to count the answers? Next is mathematical derivation.

After the final classification, the grid numbers with the same color and parity are A1, A2, ana_ 1,a_ 2,..., a_ na1​,a2​,..., an, number is B1, B2, bnb_ 1,b_ 2,..., b_ nb1​,b2​,..., bn (n > 1n > 1n > 1), so that the answer is SSS, including:

S=(a1+a2)(b1+b2)+(a1+a3)(b1+b3)+...+(a1+an)(b1+bn)+(a2+a3)(b2+b3)+...+(a2+an)(b2+bn)+...+(an−1+an)(bn−1+bn)S=(a_1+a_2)(b_1+b_2)+(a_1+a_3)(b_1+b_3)+...+(a1+a_n)(b_1+b_n)+(a_2+a_3)(b_2+b_3)+...+(a_2+a_n)(b_2+b_n)+...+(a_{n-1}+a_n)(b_{n-1}+b_n)S=(a1​+a2​)(b1​+b2​)+(a1​+a3​)(b1​+b3​)+...+(a1+an​)(b1​+bn​)+(a2​+a3​)(b2​+b3​)+...+(a2​+an​)(b2​+bn​)+...+(an−1​+an​)(bn−1​+bn​)

=∑i=1n−1aibi+a1∑i=1nbi−a1b1+a2∑i=1nbi−a2b2+...+an∑i=1nbi−anbn=\sum\limits_{i=1}^{n-1}a_ib_i+a_1\sum\limits_{i=1}^nb_i-a_1b_1+a_2\sum\limits_{i=1}^nb_i-a_2b_2+...+a_n\sum\limits_{i=1}^nb_i-a_nb_n=i=1∑n−1​ai​bi​+a1​i=1∑n​bi​−a1​b1​+a2​i=1∑n​bi​−a2​b2​+...+an​i=1∑n​bi​−an​bn​

=∑i=1n−2aibi+∑i=1nai × ∑i=1nbi=\sum\limits_{i=1}^{n-2}a_ib_i+\sum\limits_{i=1}^na_i\times\sum\limits_{i=1}^nb_i=i=1∑n−2​ai​bi​+i=1∑n​ai​ × I = 1 Σ n Bi (if the above steps cannot be understood, it is recommended to deduce it manually or take a special value to find the law)

  • When N=1, S = − a1b1+a1b1=0S=-a_1b_1+a_1b_1=0S = − a1 b1 + a1 b1 = 0, no effect.

That's easy! After classification, we can count these answers. We can directly scan O(n)O(n)O(n).

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+10,P=10007;
typedef long long LL;
LL n,m,ji[MAXN],ou[MAXN],ans; 
struct node
{
 LL number,color,under;
}a[MAXN];//Structure storage 
bool cmp(const node &fir,const node &sec)
{
 if(fir.color!=sec.color) return fir.color<sec.color;
 return fir.under<sec.under;
}
int main()
{
 scanf("%d %d",&n,&m);
 for(int i=1;i<=n;i++) a[i].under=i;//Process subscript 
 for(int i=1;i<=n;i++) scanf("%d",&a[i].number);
 for(int i=1;i<=n;i++) scanf("%d",&a[i].color);
 sort(a+1,a+n+1,cmp);//Sort by color 
 for(int i=1;i<=n;i++)
 {
  if(a[i].under&1) ji[++ji[0]]=i;
  else ou[++ou[0]]=i;
 }//Sort by parity 
 LL sgmai=a[ji[1]].under%P,sgmbi=a[ji[1]].number%P,sgmab=a[ji[1]].under*a[ji[1]].number%P,ls=a[ji[1]].color,cnt=1;
 for(int i=2;i<=ji[0];i++)
 {
  if(a[ji[i]].color!=ls)
  {
   ans=(ans+sgmai*sgmbi%P+(cnt-2)*sgmab%P)%P;
   sgmai=a[ji[i]].under%P;
   sgmbi=a[ji[i]].number%P;
   sgmab=a[ji[i]].under*a[ji[i]].number%P;
   ls=a[ji[i]].color;
   cnt=1;
  }
  else
  {
   cnt++;
   sgmai=(sgmai+a[ji[i]].under)%P;
   sgmbi=(sgmbi+a[ji[i]].number)%P;
   sgmab=(sgmab+a[ji[i]].under*a[ji[i]].number%P)%P;
  }
 }//Count the odd answers. sgmai is the sum of ai, sgmbi is the sum of bi, sgmab is the sum of ai*bi, ls represents the color currently processed, and cnt is the number. 
 ans=(ans+sgmai*sgmbi%P+(cnt-2)*sgmab%P)%P;//Don't forget to count the final answer after scanning!!! Otherwise, the last color will be missed 
 sgmai=a[ou[1]].under%P,sgmbi=a[ou[1]].number%P,sgmab=a[ou[1]].under*a[ou[1]].number%P,ls=a[ou[1]].color,cnt=1;
 for(int i=2;i<=ou[0];i++)
 {
  if(a[ou[i]].color!=ls)
  {
   ans=(ans+sgmai*sgmbi%P+(cnt-2)*sgmab%P)%P;
   sgmai=a[ou[i]].under%P;
   sgmbi=a[ou[i]].number%P;
   sgmab=a[ou[i]].under*a[ou[i]].number%P;
   ls=a[ou[i]].color;
   cnt=1;
  }
  else
  {
   cnt++;
   sgmai=(sgmai+a[ou[i]].under)%P;
   sgmbi=(sgmbi+a[ou[i]].number)%P;
   sgmab=(sgmab+a[ou[i]].under*a[ou[i]].number%P)%P;
  }
 }//Similarly 
 ans=(ans+sgmai*sgmbi%P+(cnt-2)*sgmab%P)%P;
 printf("%d\n",ans);
 return 0;
}

An easy mistake: Although the module of this problem is P=10007P=10007P=10007, it is dealing with Σ i=1n − 2aibi\sum\limits_{i=1}^{n-2}a_ib_ii=1 Σ n − 2 ai bi, due to AIA_ The maximum value of IAI is NNN (1 ≤ n ≤ 1000001 \leq N \leq 1000001 ≤ n ≤ 100000), bib_ The maximum value of IBI # is numberinumber_ The maximum value of inumberi (1 ≤ numberi ≤ 1000001 \leq number_i \leq 1000001 ≤ numberi ≤ 100000), so when processing Σ i=1n − 2aibi\sum\limits_{i=1}^{n-2}a_ib_ii=1 Σ n − 2 ai bi, the intermediate process may overflow, so it is best to open long long storage to avoid data overflow.

Conclusion: for such mathematical problems, the code size is generally not very large. The key is how to use the problem conditions to deduce, continuously optimize the algorithm (here we need a solid mathematical foundation) and finally achieve full score.

Posted by whmeeske on Sun, 22 May 2022 08:01:03 +0300