题意

给出一个整数 \(x\) 和两个数组：\(a_1,a_2,\cdots,a_n,b_1,b_2,\cdots ,b_n\)。生成一个 \(n\times n\) 的矩阵 \(M\)，定义如下：

求出矩阵 \(M\) 的行列式，模 \(10^9+7\) ，即 \(\det(M)\mod 10^9+7\)。

题目链接：https://ac.nowcoder.com/acm/contest/7502/D

分析参考：https://zhuanlan.zhihu.com/p/34685081

分析

由题意得：

对 \(M\) 进行加边升阶，有：

对于 \(M'\) 的 \(2\) 到 \(n+1\) 行，每行减去 \(a_i\) 乘第 \(1\) 行的值，得：

从第二列开始，每列乘上 \(\frac{a_i}{x}\) 后加到第 \(1\) 列上，得：

即转化为一个上三角形式，最终答案为主对角线上得元素的乘积：

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int a[N],b[N];
ll power(ll x,ll y)
{
    ll res=1;
    x%=mod;
    while(y)
    {
        if(y&1)
            res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}
int main()
{
    int x,n;
    while(scanf("%d%d",&n,&x)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+1LL*a[i]*b[i]%mod)%mod;
        ans=(power(1LL*x,1LL*n)+power(1LL*x,1LL*n-1)*ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}