当前位置 博文首页 > nameofcsdn的博客：范德蒙矩阵
目录
一，范德蒙矩阵
二，OJ实战
51Nod - 1960 范德蒙矩阵
?
LYK最近在研究范德蒙矩阵与矩阵乘法，一个范德蒙矩阵的形式如下：
它想通过构造一个含有1~nm的n*m的矩阵G，使得G*V得到的n*n的矩阵T中所有位置上的元素之和最大。其中n,m<=100000，ai<=2*10^9。
你只需输出这个值对1e9+7取模后的结果。
?
在样例中，矩阵G为
1 4
2 3
当然可能存在其它的方法使得答案最大。
Input
第一行两个数n,m，接下来一行m个数表示ai。
Output
一个数表示答案
Sample Input
2 2 2 3
Sample Output
37
思路：把G中的数当做变量，V中的数当做常数，分析各变量的系数即可。
结论：每一列的n个数的系数是一样的，不同列的系数之和ai有关
假设{ai}是递增的，那么G的第一列是1 - n，第二列是n+1 - 2n，... 第m列是n(m-1)+1 - nm
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int mod = 1000000007;
template<typename A>
A opMulti(A x, A y)
{
return x*y%mod;
}
template<typename A,typename N>
A aijiMulti(A a, N n, A(*pfunc)(A,A))
{
if(n<=1)return a;
A ans = aijiMulti(a, n/2, pfunc);
ans = pfunc(ans,ans);
if(n%2)ans = pfunc(ans,a);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
long long n,m,a[100000];
cin>>n>>m;
for(int i=0;i<m;i++)cin>>a[i];
sort(a,a+m);
long long xg=-n*(n-1)/2,xv,ans=0;
for(int i=0;i<m;i++){
if(a[i]%mod==1)xv=n;
else xv=(1-aijiMulti(a[i],n,opMulti<long long>))*aijiMulti(1-a[i],mod-2,opMulti<long long>)%mod;
xg=(xg+n*n)%mod,ans+=xg*xv%mod;
}
cout<<ans%mod;
return 0;
}?
cs