Source Code

Problem: 3529  User: JiaJunpeng 
Memory: 388K  Time: 16MS 
Language: C++  Result: Accepted 

Source Code 
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
using namespace std;
int a[21][21],b[21][21],c[40][40],m,n,t,coef[21][21][41],f[41][41],g[41][41][41];
int mod=1000000007;
long long x,y;
void gcd(int a,int b)
{
     long long temp;
     if(b==0)
     {
        x=1;
        y=0;
        return;
     }
     gcd(b,a%b);
     temp=x;
     x=y;
     y=(long long)temp-(long long)(a/b)*(long long)y;
}
int main()
{
    int i,j,ans,s,p,q,it,jt,kt,flag;
    scanf("%d%d%d",&m,&n,&t);
     for(i=0;i<=m+n;i++)
      for(j=0;j<=m+n;j++)
      {
           if(j==0||j==i)
              c[i][j]=1;
           else
              c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
      }
    memset(f,0,sizeof(f));
    f[0][1]=1;
    f[0][0]=-1;
    for(i=1;i<m+n;i++)
    {
         f[i][i+1]=1;
         for(j=i;j>=0;j--)
         {
            flag=1;
            for(s=i-1;s>=0;s--)
            {
                f[i][j]+=((long long)c[i+1][i+1-s]*(long long)flag*(long long)f[s][j])%mod;
                f[i][j]%=mod;
                if(f[i][j]<0)
                  f[i][j]+=mod;
                flag*=-1;
            }
         }
         f[i][0]=(f[i][0]-1)%mod;
         if(f[i][0]<0)
            f[i][0]+=mod;
         for(j=i+1;j>=0;j--)
         {
            gcd(i+1,mod);
            f[i][j]=((long long)f[i][j]*(long long)x)%mod;
            if(f[i][j]<0)
               f[i][j]+=mod;
         }
    }
    for(i=1;i<=m;i++)
       for(j=1;j<=n;j++)
          scanf("%d",&a[i][j]);
    for(i=1;i<=m;i++)
       for(j=1;j<=n;j++) 
          scanf("%d",&b[i][j]);
   it=m;
   jt=n;
   for(i=0;i<=it;i++)
          for(j=0;j<=jt;j++)
             for(s=0;s<i+j;s++)
                coef[i][j][s]=0;
       for(i=0;i<=it;i++)
         for(j=0;j<=jt;j++)
            for(s=0;s<=it+jt;s++)
                g[i][j][s]=0;
       for(i=1;i<=it;i++)
         for(j=1;j<=jt;j++)
         {
             for(p=1;p<i;p++)
               for(q=0;q<p+j;q++)
               {
                    coef[i][j][q]+=g[p][j][q];
                    coef[i][j][q]%=mod;
               }
             for(q=1;q<j;q++)
               for(p=0;p<i+q;p++)
               {
                    coef[i][j][p]+=g[i][q][p];
                    coef[i][j][p]%=mod;
               }
             coef[i][j][0]+=b[i][j];
             coef[i][j][0]%=mod;     
             for(s=0;s<=i+j-2;s++)
             {
                 int value=((long long)a[i][j]*(long long)coef[i][j][s])%mod;
                 for(p=0;p<=s+1;p++)
                 {
                    g[i][j][p]+=((long long)value*(long long)f[s][p])%mod;
                    g[i][j][p]%=mod;
                 }
             }
         }
    while(t--)
    {
        scanf("%d%d%d",&it,&jt,&kt);
        ans=0;
        for(i=it+jt-2;i>=0;i--)
        {
            int value=((long long)kt*(long long)ans)%mod;
            ans=(value+coef[it][jt][i])%mod; 
        }
    
        printf("%d\n",ans);
    }
    return 0;
}