题目

分析

一步步删掉循环，

首先，原式是$$\sum_{i=1}^n\sum_{j=1}m\sum_{k=i}^n\sum_{l=j}m\sum_{p=i}^k\sum_{q=j}l1$$

删掉最后两个循环

\[\sum_{i=1}^n\sum_{j=1}^m\sum_{k=i}^n\sum_{l=j}^m(k-i+1)(l-j+1)
\]

发现，当$i,j$固定，随着$k,l$的变化，$(k-i+1),(l-j+1)$都是每次减少1

SO，

\[\sum_{i=1}^n\sum_{j=1}^m[1+2+···+(n-i+1)][1+2+···+(m-j+1)]
\]

再根据等差数列求和公式，

\[\sum_{i=1}^n\sum_{j=1}^m\dfrac{(n-i+1)(n-i+2)(m-j+1)(m-j+2)}{4}
\]

又发现$\sum_{i=1}^n(n-i+1)(n-i+2),$其实就是$1*2+2*3+3*4+···+n*(n+1)$

设其为$g(n)$,$m$类似

答案就是$\dfrac{g(n)*g(m)}{4}$

接着考虑求$g(n)$

\[=1^2+1+2^2+2+3^2+3+···+n^2+n
\]

\[=1^2+2^2+3^2+···+n^2+1+2+3+···+n
\]

根据自然数幂和得

\[=\dfrac{n(n+1)(2n+1)}{6}+\dfrac{n(n+1)}{2}
\]

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const long long mo=1000000007;

const int N=10000005;

using namespace std;

long long ans,n,m,ny4,ans1,ans2,ny6;

long long mi(long long x,long long y)

{

	long long sum=1;

	while(y)

	{

		if(y&1) sum=sum*x%mo;

		x=x*x%mo;

		y/=2;

	}

	return sum;

}

int main()

{

	scanf("%lld%lld",&n,&m);

	n%=mo;

	m%=mo;

	ny4=mi(4,mo-2);

	ny6=mi(6,mo-2);

	ans1=((n*(n+1)%mo*(2*n+1)%mo*ny6%mo)+(n+1)*n/2%mo)%mo;

	ans2=((m*(m+1)%mo*(2*m+1)%mo*ny6%mo)+(m+1)*m/2%mo)%mo;

	printf("%lld",ans1*ans2%mo*ny4%mo);

}

巴特西

【NOIP2016提高A组模拟10.15】算循环

题目

分析

最新文章

热门文章