商业网站开发入门选课,律所网站建设,营销推广型网站公司,深圳注册公司地址有什么要求题目描述 输入 输出 样例输入 167 198 样例输出 906462341 数据范围 解法 令f(n)∑ni1i#xff0c;g(n)∑ni1i2 易得ans∑ni1∑mj1f(n−i1)∗f(m−j1) 等价于ans∑ni1∑mj1f(i)∗f(j) 显然f(n)n∗(n−1)/2#xff1b; 拆开得ans14∑ni1∑mj1i∗(i1)∗j∗(j1) 再得ans14∑… 题目描述 输入 输出 样例输入 167 198 样例输出 906462341 数据范围 解法 令f(n)∑ni1ig(n)∑ni1i2 易得ans∑ni1∑mj1f(n−i1)∗f(m−j1) 等价于ans∑ni1∑mj1f(i)∗f(j) 显然f(n)n∗(n−1)/2 拆开得ans14∑ni1∑mj1i∗(i1)∗j∗(j1) 再得ans14∑i1ni∗(i1)∗∑j1mj∗(j1)14∑i1n∗(f(i)g(i))∗∑j1m∗(f(j)g(j)) 其中g(n)16n(n1)(2n1) 时间复杂度为O(log)逆元有复杂度。 代码 #includeiostream
#includestdio.h
#includemath.h
#includestring.h
#includealgorithm
#define ll long long
#define ln(x,y) ll(log(x)/log(y))
#define sqr(x) ((x)*(x))
using namespace std;
const char* finloop.in;
const char* foutloop.out;
const ll inf0x7fffffff;
const ll mo1000000007;
ll n,m,i,j,k,l,tmp,tmd,num,ans;
ll qpower(ll a,ll b){ll c1;while (b){if (b1) ca*c%mo;aa*a%mo;b1;}return c;
}
ll N(int a){return qpower(a,mo-2);
}
ll sum(ll st,ll num){st%mo;num%mo;ll en(stnum-1)%mo;return (sten)%mo*num%mo*N(2)%mo;
}
ll xsum(ll n){n%mo;return n*(n1)%mo*(2*n1)%mo*N(6)%mo;
}
ll count(ll v){return (sum(1,v)xsum(v))%mo;
}
int main(){freopen(fin,r,stdin);freopen(fout,w,stdout);scanf(%lld%lld,n,m);anscount(n)*count(m)%mo*N(4)%mo;printf(%lld,ans);return 0;
} 启发 ∑的运算性质 1.∑(ab)∑a∑b 2.∑a∑ba∗b∑aa∗∑bb 3.∑ik∗f(i)k∗∑f(i) ∑ni1i2公式 ∑ni1i216n(n1)(2n1) 证明 利用数学归纳法检验。 设g(n)∑ni1i2 先有g(1)16∗1∗2∗31∑i1ni2 如果g(x)满足g(x)16x(x1)(2x1) 则g(x1)16x(x1)(2x1)(x1)216(x1)(6x6x(2x1))16(x1)(2x27x6)16(x1)(x2)(2x3)16(x1)[(x1)1][2(x1)1] 综上得证。 转载于:https://www.cnblogs.com/hiweibolu/p/6714869.html
