matrix(找规律)
然而一个一个的暴力,显然可以得60分=。=
10^5,一看就o(n)。。。。
你先只考虑n = 3,观察第一行每个数和第一列每个数的贡献。
因为f[i][j]是由f[i-1][j]和f[i][j-1]得到的。所以第一行第一个是没有贡献的。
第一行的第j个数会乘n-1个b和n-j个a..就会到n行n列上。
在乘上它用几种方法走到n行n列上。就是每个数的贡献
第一列同理。
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long n, a, b,aa[100005],bb[100005],f[200005],inv[200005];
void read(long long &x)
{
x = 0;
int ff = 0;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') ff = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
if(ff) x = -x;
}
long long mpow(long long aaa,long long bbb)
{
long long rt = 1;
for( ; bbb; bbb >>= 1, aaa = aaa * aaa % mod)
if(bbb & 1) rt = rt * aaa % mod;
return rt;
}
long long c(int n,int m)
{
return f[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
long long ans = 0;
read(n);read(b);read(a);
f[0] = f[1] = inv[0] = inv[1] = 1;
for(int i = 2; i <= 2*n; i++)
{
f[i] = 1ll * f[i-1] * i % mod;
inv[i] = 1ll * (mod - mod/i) * inv[mod%i] % mod;
}
for(int i = 2; i <= 2*n; i++)
{
inv[i] = inv[i] * inv[i-1] %mod;
}
aa[0] = 1; bb[0] = 1;
for(long long i = 1; i <= n; i++)
{
aa[i] = mpow(a,i); bb[i] = mpow(b,i);
}
for(long long i = 1; i <= n; i++)
{
long long he;
read(he); if(i == 1) continue;
long long ha = c(2*n - i - 2,n-i);
he = he * bb[n-1] % mod * aa[n-i] %mod * ha %mod;
ans = (ans + he) % mod;
}
for(long long i = 1; i <= n; i++)
{
long long he;
read(he);if(i == 1) continue;
he = he * aa[n-1] % mod * bb[n-i] %mod* c(2*n - i - 2,n-i)%mod;
ans = (ans + he) % mod;
}
printf("%lld",ans);
return 0;
}