目录

一，范德蒙矩阵

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

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/116990211