数列グループ数の合計(HDU 5490 Simple Matrix)

Simple Matrixタイトル接続
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 128 Accepted Submission(s): 35
Problem Description As we know, sequence in the form of an=a1+(n−1)d is called arithmetic progression and sequence in the form of bn=b1qn−1(q>1,b1≠0) is called geometric progression. Huazheng wants to use these two simple sequences to generate a simple matrix. Here is what he decides to do: Use the geometric progression as the first row of the simple matrix: c0,n=bn Use the arithmetic progression as the first column of the simple matrix: cn,0=an Calculate the item at n-th row, m-th column of the simple matrix as cn,m=cn−1,m+cn,m−1, where n≥1 and m≥1. Given the two sequences, Huazheng wants to know the value of cn,m, but he is too busy with his research to figure it out. Please help him to work it out. By the way, you can assume thatc0,0=0.
Input The first line of input contains a number T indicating the number of test cases (T≤200). For each test case, there is only one line containing six non-negative integers b1,q,a1,d,n,m. (0≤n≤10000). All integers are less than 231.
Output For each test case, output a single line consisting of “Case #X: Y”.X is the test case number starting from 1. Y is cn,m module 1000000007.
Sample Input 2 3 10 1 1 3 3 5 2 1 10 4 2
Sample Output Case #1: 423 Case #2: 140
Source 2015 ACM/ICPC Asia Regional Hefei Online
題意略構想:境界行は等比数列,列は等差数列であり,境界の総和への寄与は行,(n+m−in),列(m+n−im)では求められる
c(n,m)=∑i=0nai(m+n−im)+∑i=0mbi(m+n−in)
プッシュを使用:
(nk) =
(n−1k−1) +
(n−1k)
最後の等差部分の結果は次のとおりです.
S等差=a 1(m+n+1 n)+d(m+n+1 n+2)
等比部分はプッシュで使用できます.
Sn=q∗sn−1q−1−(m+nn)q−1
内
S1=q(q(m+1)−1)(q−1)2−m+1q−1
ここの
(m+nn)は先に処理できます
逆元は繰返しで前処理することができる.

/*************************************************************************
    > File Name: hefei/1007.cpp
    > Author: kelvin
    > Mail: 444051232@qq.com
    > Created Time: 2015 09 27      16 11 15 
 ************************************************************************/

#include<iostream>
#include<cmath>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<utility>
#include<stdio.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;++i)
#define LL long long
#define mset(a,b) memset(a,b,sizeof a)

const LL p=1000000007;
const int maxn=10011;
LL b,q,a,d,m,n;
LL invq;
LL expp2;
LL C[maxn];
LL invv[maxn];

LL gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b)  {d=a;x=1;y=0;}
    else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
}

LL inv(LL a)
{
    LL d,x,y;
    gcd(a,p,d,x,y);
    return d==1?(x+p)%p:-1;
}

LL getinv()
{
    invv[1]=1;
    REP(i,2,maxn)
    {
        invv[i]=(p-p/i)*invv[p%i]%p;
    }
}

LL exp_mod(LL a, LL b) {
    LL res = 1;
    while(b != 0) {
        if(b&1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}


LL Comb(LL a, LL b) {
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    LL ans = 1, ca = 1, cb = 1;
    for(LL i = 0; i < b; ++i) {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*exp_mod(cb, p - 2)) % p;
    return ans;
}

LL Lucas(int n, int m) {
     LL ans = 1;

     while(n&&m&&ans) {
        ans = (ans*Comb(n%p, m%p)) % p;
        n /= p;
        m /= p;
     }
     return ans;
}

void getC()
{
    C[0]=1;
    C[1]=(m+1)%p;
    REP(i,2,n+3)
    {
        C[i]=(((m+i)*C[i-1])%p)*invv[i];
        C[i]%=p;
        if(C[i]<0)  C[i]+=p;
    }
}

LL solve()
{
    invq=inv(q-1);
    LL ans;
    LL sm;
    if(q==1)
        sm=(b*Lucas(m+n+1,n+1))%p;
    else{
        getC();
        LL sp=(q*((exp_mod(q,m+1)-1+p)%p)%p*invq%p*invq)%p-(m+1)*invq%p;
        sp%=p;
        if(sp<0)    sp+=p;
        sm=sp;
        REP(i,2,n+1)
        {
            sm=(((q*sm)%p*invq)%p-(C[i]*invq)%p+p)%p;
        }
        sm=(sm*b)%p;
        if(sm<0)    sm+=p;
    }
    ans=sm;
    LL tmp=(a*Lucas(m+n+1,m+1))%p;
    ans+=tmp;
    tmp=(d*Lucas(m+n+1,m+2))%p;
    ans+=tmp;
    ans%=p;
    if(ans<0)   ans+=p;
    return ans;
}

int main()
{
    int t,cas=1;
    getinv();
    scanf("%d",&t);
    while(t--)
    {
        LL ans;
        scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&b,&q,&a,&d,&n,&m);
        //cin>>b>>q>>a>>d>>n>>m;
        b%=p;q%=p;a%=p;d%=p;
        if(m==0 && n==0)
        {
            ans=0;
        }
        else if(n==0)
        {
            ans=b*exp_mod(q,m-1);
            ans%=p;
        }
        else if(m==0)
        {
            ans=a+(n-1)*d;
            ans%=p;
        }
        else{
            m--;n--;
            ans=solve();
        }
        printf("Case #%d: %I64d
",cas++,ans);
    }
}