目录

一，范德蒙矩阵

二，OJ实战

51Nod - 1960 范德蒙矩阵

---

一，范德蒙矩阵

 

二，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;
}