マトリックス乗算最適化DP

2741 ワード
日常の水
久しぶりにブログを更新して、更新して、ついでに自分にも少し熟知させます.noip向上のためにrpを貯める.
マトリクスについて説明します.x*yの縦横2ビットデータテーブルです.例えば、2*2の行列Aは、{(1,2)(3,4)}
ではその中でA(0,1)は2で、このようにして...
最も基本的な行列を紹介した後、行列乗算について話します.マトリクス乗算は2つのマトリクスを乗算します.ただし、マトリクスA*Bなどの制限があります.ここで、Aの大きさがa*bであれば、Bの大きさはb*cでなければならない.
どうしてですか.乗算の過程についてお話しします.A*B=Cの場合、C(i,j)=すべてのA(i,k)*B(k,j)の和.Aの列数とBの行数はいずれもkに等しいので、Aの列数はBの行数に等しいことがわかる.
またA(a*b)*B(b*c)=C(a*c)という例も上の例から容易に見られる.
マトリクス乗算をコードに変換すると容易に実現できる.以下(以下、A(n*t)、B(t*m)の場合):
for(int i=0;i

このような一次行列乗算の時間的複雑さはO(n^3)である.a[i][k]=0の場合、必ず計算しなくてもいいので、加算結果はすべて0なので、このように変更することができます.
for(int i=0;i

そして,行列乗算は結合則のみであり,交換則はない.A*B*C=A*(B*C)ですが、A*B!=B*A.乗算の過程によって考えてみると、なぜか分かります.
結合則があるので,行列は高速べき乗が可能であると述べた.多くの問題を解決することができます.
例題:洛谷1962転送ゲート:https://www.luogu.org/problemnew/show/P1962.
フィボナッチ数列のn番目の項%1億07,000万の値を求めます.nはlonglong範囲内である.
フィボナッチ数列からdp方程式が得られる:f[i]=f[i-1]+f[i-2],nはそんなに大きくて、どうしますか?このとき,各f[i]について,彼の結果はf[i−1]+f[i−2]であり,行列乗算が可能であることが分かった.
行列A(1*2)でシーケンスのi番目とi+1番目を表し,シーケンスのi+1番目とi+2番目をC(1*2)で表す.
では、行列乗算A*B(2*2)=Cに従います.私たちはBを求めなければなりません.
まずC(0,0)=A(0,0)*B(0,0)+A(0,1)*B(1,0)は,C(0,1)がシーケンスのi+1番目の項であり,A(0,1)もシーケンスのi+1番目の項であることから,B(1,0)=1,B(0,0)=0となる.
そして、C(0,1)=A(0,0)*B(0,1)+A(0,1)*B(1,1),C(0,1)はシーケンスのi+2番目の項であり、dp方程式によれば、C(0,1)=A(0,0)+A(0,1)である.したがってB(0,1)=1,B(1,1)=1となる.
こうしてBが出てきたのが、{(0,1)(1,1)}です.初期の2項については,n−1回Bを乗じると最終的なnとn+1項が得られる.しかし,行列には結合則があり,中間は高速べき乗で乗算でき,タイムアウトは起こらない.
このように分析すると、コードが出てきます.
#include
using namespace std;
#define mod 1000000007LL
struct matrix{  //    
    long long a[2][2];
    matrix(){
        for(int i=0;i<2;i++)
          for(int j=0;j<2;j++) a[i][j] = 0LL;
    }
}t,d;
matrix operator * (matrix a,matrix b)  //       ，            。
{
    matrix c;//           。
    for(int i=0;i<2;i++)
      for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
          c.a[i][j] =(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
    return c;
}
matrix qpow(matrix now,long long x)  //   。
{
    if(x==1LL) return now;
    matrix c = qpow(now , x>>1);
    if(x&1)return c*c*now;
    else return c*c;
}
int main()
{
    long long n;
    matrix ans;
    scanf("%lld",&n);
    if(n==1)
    {
        printf("1");
        return 0;
    }
    t.a[0][0]=t.a[0][1]=d.a[0][1]=d.a[1][1]=d.a[1][0]=1LL;  //t     ，d      B。
    ans = t * qpow(d,n-1LL);
    printf("%d",ans.a[0][0]%mod);
    return 0;
}

このようなフィボナッチ数列は行列乗算最適化DPにおいて非常に基礎的である.しかしDPの方程式を見つければ,f[i]毎の答えが同じであるという特徴があれば,詳細な解析を経て,ほとんどがこのような行列乗算に変換してDPを最適化することができる.
2つの多次元配列をkey値で1つの列を取り出し、2つの配列を結合して再計算します.
HTMLに書くURI