Matrix 【NOIP2016提高A组模拟8.17】

题目

样例输入：

4 3 5
4 1 7 3
4 7 4 8

样例输出：

59716

数据范围：

---

剖解题目

被虐，不多说了QwQ~~

---

思路：

这种题目，光看数据范围就知道暴力肯定不行，肯定是有规律或者公式的，努力推推看。
然而比赛上我推了好久好久，推出了个滑稽的公式，哭晕+_+|||。

---

解法

40%：暴力。
60%：当a=0时，左边的数不会对右边的数有影响，未知数只会受到上方数的影响，答案就是第一行最后的数乘（n-1）个b。
100%：从60%数据中，我们的思路已经是转换成了研究一个位置对答案的影响了，而不是去傻傻的暴力，我们继续沿着这个思路。
其实每一个格子的数都会转化成第一行与第一列的数，经过一番推后。对于一个位置，每向右移动一位，就得乘一个a；每向下移动一位，就得乘一个b，并且发现这个贡献还和当前位置到达目标位置的路径方案数有关。
路径方案数是 Cn−2n∗2−i−2 ，假设我们是计算第一行对答案的贡献，那么第i位对答案贡献是:
Ans=Cn−2n∗2−i−2∗an−i∗bn−1 。
计算第一列也是同理，把a与b的次方数反过来就行了。

注意：在计算组合数时，因为有模，所以按照公式算是行不通的，需要用到逆元。

---

代码

#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define ll long long

using namespace std;

const int maxn=100005,mo=1e9+7;
ll h[maxn],l[maxn],n,a,b,ans,G[maxn*2],ny[maxn*2];

ll qsm(ll a,ll b)
{
    ll t=1,y=a;
while (b) {
if (b&1) t=t*y%mo;
y=y*y%mo;
        b>>=1;
    }
return t;
}
ll C(ll n,ll m)
{
    ll sum=G[m]*ny[n]%mo*ny[m-n]%mo;
//  ll sum=G[m]/(G[n]*G[m-n]);
return sum;
}
int main()
{
//freopen("T1.in","r",stdin);
    G[0]=1;
    scanf("%lld%lld%lld",&n,&a,&b);
    fo(i,1,n) {
        scanf("%lld",&l[i]);
        G[i]=(G[i-1])*i%mo;
        ny[i]=qsm(G[i],mo-2);

    }
    fo(i,1,n){
        scanf("%lld",&h[i]);
        G[i+n]=(G[i+n-1])*(i+n)%mo;
        ny[i+n]=qsm(G[i+n],mo-2);
    }
if (n==1) printf("%lld",l[1]);
else {
        ny[0]=1;
        fo(i,2,n) {
            ll aa=qsm(a,n-1),bb=qsm(b,n-i);
            ll c=C(n-2,2*n-i-2);
            ans=(ans+c*aa%mo*bb%mo*l[i]%mo)%mo;
            aa=qsm(a,n-i),bb=qsm(b,n-1);
            ans=(ans+c*aa%mo*bb%mo*h[i]%mo)%mo;
        }
printf("%lld",ans);
    }
}