【牛客7502 D行列式】

传送门
更好的阅读体验点这里

题意

求一个n阶行列式的值，行列式第行第列的元素是,特别的时，需要额外加上一个x
a和b是两个给定的长度为n的数组，x是一个给定的数。如图

题解

这道题最主要的就是关于这个行列式的化简用到了一个小技巧：升阶法

来源：我是从这里学到的！猪真是个好地方针不戳针不戳

具体方法是在最左边和最上面加一行一列，让n阶行列式变为n+1阶行列式，第一列除第一行的位置其他全为0，第一行除第一列的位置其他全为b[1]~b[n]，如图

这样升阶后，把第一行分别乘上加到第行去，这样一来行列式除第一行第一列的部分就变成了主对角线全为x，其他部分全为0，如图
这样就转化成了一种叫做箭型行列式的行列式（只有第一行第一列和主对角线元素不为0，像一个箭头），这种行列式的解法就是把第2列~第n+1列，每一列乘上加到第一列去
这样行列式的第一列除第一行就全为0了，第一列第一行的元素从原来的1，变为了，，如图

然后按第一列展开，行列式的值即为。

因为除去第一行第一列后的行列式是一个上(下)三角行列式，所以行列式的值为主对角元素之和

坑点

x=0时，显而易见由于主对角线上没有多余的数x加上去，这样就使得任意两行元素都是存在倍数关系的，根据行列式的性质，两行成倍数的行列式值为0，显然x=0时，行列式的值为0.

但是需要特别注意,我们说的两行成比例,那也得有两行才行,n=1,x=0时行列式的值不为0,而是等于唯一的元素的值.

说明

菜鸡没有找到markdown怎么打出行列式左右两竖线,就用矩阵的方括号代替了,望各位看博客的聚聚们见谅!

Code

/****************************
* Author : W.A.R            *
* Date : 2020-10-31-19:12   *
****************************/
/*
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define show(x) std:: cerr << #x << " = " << x << std::endl;
#define mem(a,x) memset(a,x,sizeof(a))
#define Rint register int
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int maxm=2e6+10;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double eps=1e-7;
ll qpow(ll a,ll n){a%=mod;ll ans=1;while(n){if(n%2)ans=ans*a%mod;n/=2;a=a*a%mod;}return ans;}

ll a[maxn],b[maxn];
int main(){
    ll n,x;
    while(scanf("%lld%lld",&n,&x)!=EOF){
        ll tmp=qpow(x,n-1),ans=tmp*x%mod,tt=0;
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
        for(int i=1;i<=n;i++)tt=(tt+a[i]*b[i]%mod)%mod;
        ans=(ans+tmp*tt%mod)%mod;
        printf("%lld\n",ans);                   
    }
    return 0;
}