BZOJ 3240[Noi 2013]マトリックスゲーム問題解

転載は以下のことを明記してください.http://blog.csdn.net/jiangshibiao/article/details/24594825
【原題】
3240:[Noi 2013]マトリックスゲーム
Time Limit: 10 Sec  
Memory Limit: 256 MB
Submit: 336  
Solved: 158
[ Submit][ Status]
Description
??はマトリクスが好きな子供で、ある日彼女はパソコンで巨大なn行m列のマトリクスを生成したいと思っています(彼女がどのように保存するか心配しないでください).彼女が生成したこの行列は、行列のi行目j列の要素をF[i][j]で表すと、F[i][j]は次の繰返し式を満たす:F[1][1]=1 F[i,j]=a*F[i][j-1]+b(j!=1)F[i,1]=c*F[i-1][m]+d(i!=1)繰返し式のa,b,c,dはいずれも所定の定数である.今??はF[n][m]の値がいくらなのか知りたいので、助けてください.最終的な結果が大きい可能性があるため、F[n][m]を100000007で割った余剰を出力するだけです.
Input
1行には6つの整数n,m,a,b,c,dがある.意味は題のとおりである
Output
F[n][m]を1000000007で割った剰余を表す整数を含む
Sample Input
3 4 1 3 2 6
Sample Output
85
HINT
サンプルのマトリクスは、1 4 7 10 26 29 32 35 76,7982,85です.

【前言】NOI~~この私が以前から憧れていた名詞が、こんなに近くにいるなんて~~思い切って、この問題を作ることにしました.周りの大神がいろいろな行列で秒を乗算していたので、私のこんにゃくはゆっくり切るしかありませんでした.
公式は自分で押したが、コードはあまりにも複雑で、牛にいくつかのコードの参考をした.
【分析】私たちはまず簡単なことから押します.最初の行を考えます.
等比数列に基づいて通項式を出すことができます(紙にストロークすればいいです)
しかし、これは第一歩にすぎない.
上記の式は実際にはf[i][x]に確立されている.
f[i][m]とf[i+1][1]の公式によれば、f[i+1][1]とf[i][1]の関係を打ち出すことができる.(実はcに乗ってdを加えればいいのですが)

そして法則を見つけたのではないでしょうか.a,b,c,dに関するすべてを定数として,この式は一番上の式になることができる!これにより,f[x][1]の値を容易に求めることができる.
その後、f[n][1]を求めてf[n][m]に渡す2つの方法がある.f[n+1][1]を求めた後、dをcで減算する.
2つ目を選びました.少し速くなりましたが、逆元を求めます.(こんな分までやったのに、逆元もそうだった)
これで終わりです.
【注意】1 nとmの範囲が広いので,フェマの小さな定理を用いる.

これにより,nを先に(p−1)型を取り,計算することができる.
②a=1の場合は特審.
【コード】

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MaxN=1000010;
const ll MOD=1000000007;
char s[MaxN],t[MaxN];
struct arr{ll uni,ord;}n,m;  //uni  a=1   ，ord  a≠1   
ll a,b,c,d,p,k,t;
void give(char *s,arr &n)
{
    int p=strlen(s);
    for (int i=0;i<p;++i)
    {
        n.uni=(n.uni*10+s[i]-48)%MOD;   
        n.ord=(n.ord*10+s[i]-48)%(MOD-1);
    }
}
ll power(ll x,ll y)           //   
{
    ll res=1ll;
    while (y)
    {
      if (y&1ll) res=res*x%MOD;
      y=y/2ll;x=x*x%MOD;
    }
    return res;
}
ll ni(ll x)
{
  return power(x,MOD-2);
}
 
int main()
{
    scanf("%s%s",s,t);
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    give(s,n);give(t,m);
    if (a==1)
    {
        b=((m.uni-1)*b%MOD*c+d)%MOD;
        a=c;
    }
    else
    {
        k=b*ni(a-1)%MOD;                       //    
        t=power(a,m.ord-1);
        a=c*t%MOD;
        b=((t-1)*k%MOD*c+d)%MOD;
    }
    if (a==1)
    {
        p=(1+n.uni*b)%MOD;
    }
    else
    {
        k=b*ni(a-1)%MOD;
        t=power(a,n.ord);
        p=(t+(t-1)*k)%MOD;                     //    
    }
    printf("%lld",((p-d)*ni(c)%MOD+MOD)%MOD);  //    
    return 0;
}