マトリックス連乗matrix 67大牛から
6963 ワード
一部の画像はリンクに貼られていないでしょう.http://www.matrix67.com/blog/archives/276
今のところこの方面のテーマの総括はまだないようです.ここ数日、このような質問をしている人を4人連続で見て、今日はここで簡単に書きます.ここでは他の行列に関する知識を紹介せず,行列乗算と相関特性のみを紹介する. 数学のマトリックスも黒い画面で絶えず変化する緑の文字だとは思わないでください.数学では,1つの行列が2次元配列であることを明らかにした.1つのn行m列のマトリクスにm行p列のマトリクスを乗じることができ、結果はn行p列のマトリクスであり、i行j列目の位置の数は、前のマトリクスi行目のm数と、後のマトリクスj列目のm数とが乗じたすべてのm積の和に対応する.例えば、次の式は、2行2列の行列に2行3列を乗じた行列を表し、その結果、2行3列の行列となる.このうち、結果の4は2*2+0*1に等しい. 次の式は、1 x 3の行列に3 x 2を乗じた行列であり、1 x 2の行列を得る. マトリックス乗算の2つの重要な性質:1、マトリックス乗算は交換法則を満たさない;二、行列乗算は結合法則を満たす.なぜ行列乗算は交換法則を満たさないのですか?くだらないことを言うと、交換してから2つのマトリクスが乗算できない可能性があります.なぜ結合法則を満たしているのでしょうか.よく考えてみると、これもくだらない話だと気づきます.3つの行列A、B、Cがあると仮定すると、(AB)CおよびA(BC)の結果のi行目j列の数は、すべてのA(ik)*B(kl)*C(lj)の和(すべてのkおよびlを列挙する)に等しい.古典問題1はn個の点,m個の操作を与え,O(m+n)を構築するアルゴリズムはm個の操作後の各点の位置を出力する.移動、スケール、反転、回転の操作 ここでの操作はすべての点を同時に行う.ここで、反転は座標軸を対称軸として反転し(両方の場合)、回転は原点を中心とします.各点を別々にシミュレーションすると,m個の動作に合計O(mn)がかかる.マトリクス乗算により、O(m)の時間内にすべての操作を1つのマトリクスにマージし、各ポイントをマトリクスに乗算すると、最終的なポイントの位置が直接得られ、合計O(m+n)が消費される.初期の点の座標がxとyであると仮定すると、次の5つのマトリクスは、それぞれ平行移動、回転、反転、回転操作を行うことができます.あらかじめすべてのm個の操作に対応する行列をすべて乗じておき,(x,y,1)を乗じると,最終点の位置が一歩で得られる. 古典的なテーマ2与えられた行列Aは、A^n(n個のAを乗算)の結果を迅速に計算し、出力された各数mod pを計算してください. 行列乗算には結合則があるため、A^4=A*A*A*A=(A*A)*(A*A)=A^2*A^2となる.nが偶数の場合,A^n=A^(n/2)*A^(n/2);nが奇数である場合、A^n=A^(n/2)*A^(n/2)*A(n/2が整数である).これは,A^nの計算においても2分高速べき乗を求める方法を用いることができることを示している.例えば、A^25の値を算出するには、A^12、A^6、A^3の値を再帰的に算出するだけでよい.ここでのいくつかの結果によれば,計算中に絶えず型を取り,高精度演算を避けることができる.クラシックテーマ3 POJ 3233(ありがとうrmq) 行列Aを与えて、A+A^2+A^3+...+A^kの結果を求めます(2つの行列の加算は対応する位置がそれぞれ加算されます).出力データmod m.k<=10^9. この問題は2回2点で,かなり古典的だ.まず、A^iは2点で求めることができることを知っています.そして,問題全体のデータ規模kを二分する必要がある.例えば、k=6の場合、 A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) この式を適用すると,規模kは半分に減少した.A^3を2点求めてA+A^2+A^3を再帰的に計算すると,元の問題の答えが得られる.クラシックテーマ4 VOJ 1049 順次m個の置換を与え、このm個の置換を繰り返して初期シーケンスを操作し、k回の置換後のシーケンスを尋ねる.m<=10, k<2^31. まず、このm個の置換を「マージ」し(このm個の置換の積を算出する)、次に、この置換k/m回を実行する必要がある(整数を取り、残数があればシミュレーションを数歩残しておけばよい).なお、いずれの置換もマトリクスの形式で表すことができる.たとえば、1 2 3 4を3 1 2 4に置き換え、次の行列乗算に相当します. 置換k/m回は、k/m個を前に乗じた行列に相当する.この行列のk/m次方程式を二分して計算し,初期シーケンスを乗じることができる.作ったのは忙しくて喜ばないで、得意な时はあなたが灭亡する日で、最后にいくつかの置換がシミュレーションする必要があることを忘れないでください.経典の題目5《アルゴリズム芸術と情報学の競争》207ページ(2.1代数の方法と模型,[例題5]細菌,版次が異なる可能性のあるページ番号に偏差がある) みんな自分で見に行きましょう.本には詳しく書かれています.解題方法は前の問題と類似しており,いずれも行列で操作を表し,次いで最終状態を二分して求める.経典の題目の6はnとpを与えて、第n個のFibonacci数mod pの値を求めて、nは2^31を上回らない 前のいくつかの考え方によれば、(a,b)を乗じた結果(b,a+b)になるように2 x 2の行列を構築する必要がある.この行列を1回多く乗算するたびに、この2つの数は1回多く反復されます.では,この2 x 2の行列をn回自乗し,(0,1)を乗じるとn番目のFibonacci数が得られる.考えなくても、この2 x 2の行列は簡単に構築できます. クラシックテーマ7 VOJ 1067 上記の方法では、右上隅の(n−1)*(n−1)の小行列の主対角線に1、行列のn行目に対応する係数を記入し、他の場所に0を記入するように構成された任意の線形繰返し式のn項を二分して求めることができる.例えば,f(n)=4 f(n−1)−3 f(n−2)+2 f(n−4)のk番目の項を次の行列乗算で二分的に計算することができる. 行列乗算を利用して線形繰返し関係を解く問題はトラックを作ることができる.ここで示した例題は係数がすべて1の場合である.経典の題目8は1つの有向図を与えて、A点からちょうどk歩(繰り返して辺を通ることを許す)を歩いてB点の方案数mod pの値に着きます 与えられた図を隣接行列、すなわちA(i,j)=1に変換し、1つのエッジi->jが存在する場合にのみ行う.C=A*Aとすると、C(i,j)=ΣA(i,k)*A(k,j)は、実際には、点iから点jまでちょうど2辺を通る経路数(kを中継点と列挙する)に等しい.同様に、C*Aのi行目j列目は、iからjまで3辺を通過する経路数を示す.同様に,kステップを通過する経路数を要求すれば,A^kを2点で求めるだけでよい.経典の題目9は1 x 2のドミノの骨牌でM x Nの矩形を埋め尽くして何種類の方案があって、M<=5、N<2^31、解答mod pの結果を出力します M=3を例に説明します.この矩形をパソコンの画面に横に置いて、右から左へ一列に塗りつぶしたとします.ここで、前のn-2列はすでに満たされており、第n-1列はバラツキがある.今私たちがしなければならないことは、n-1列目も埋め尽くし、n列目に状態を移すことです.n−1列目の状態が異なる(8つの異なる状態がある)ため,状況別に議論する必要がある.図の中で、私は移転前の8種類の異なる状態を左に置いて、移転後の8種類の異なる状態を右に置いて、左のある状態は右のある状態に移ってそれらの間に1本の線をつなぐことができます.シナリオが繰り返されないことを保証するために、ステータス遷移時にn−1列目にドミノの骨牌(例えば、左の2番目のステータスが右の4番目のステータスに移行できない)を縦に置くことは許されない.そうしないと、これは別の遷移前のステータスと繰り返される.この8つの状態の遷移関係を有向図に描くと,問題は,状態111から,ちょうどnステップを経てこの状態に戻るのにどれだけのスキームがあるかということになる.例えば、n=2の場合、111->011->111、111->110->111、111->000->111の3つのスキームがあり、これはドミノの骨牌で3 x 2の矩形を覆うスキームに対応している.これでこの問題は私たちの前の例題8に変わりました. 後でこの問題のソースコードを書きました.ビット演算に関するアプリケーションを再び見ることができます.クラシックテーマ10 POJ 2778 問題は、すべての可能なnビットDNA列に指定されたウイルス断片が含まれていないDNA列がどれだけあるかを検出することである.合法的なDNAはACTGの4文字でしか構成できない.テーマは10個以内のウイルス断片を与え,各断片の長さは10を超えない.データ規模n<=2000,000,000. 以下の説明では、ATC、AAA、GGC、CTの4つのウイルス断片を例に、上記の問題のように構図を通じて問題を例題8に変換する方法を説明します.我々はすべてのウイルス断片の接頭辞を探し出して、n位DNAを以下の7種類に分けます:ATで終わります、AAで終わります、GGで終わります、以?Aで終わる?Gで終わるCエンディングと以?末尾.疑問符は「その他の状況」を表し、このアルファベットがウイルスの接頭辞にならない限り、任意のアルファベットであってもよい.明らかに、これらの分類は全集の1つの区分(交差は空で、集合は全集)である.現在,n−1の長さの各DNAのうち要求に合致するDNAの個数を知っていれば,nの長さの各DNAの個数を求める必要がある.各タイプ間の遷移に基づいてエッジ上の重み付き有向図を構築することができる.例えば、ATからAAに移行できず、ATから?4つの方法(後に任意のアルファベットを追加)があります.AからAAに移行するには1つの案(後にAを加える)があります.Aから?GGから?2つの案(後にCを加えるとウイルスの断片を構成し、合法ではなく、AとTを加えるしかない)などがある.この図の構造過程は有限状態オートマチックをシリアルマッチングすることと類似している.次に,この図をマトリクスに変換し,このマトリクスをn回乗算すればよい.最後に出力されたのは??ステータスから他のすべてのステータスへのパス数の合計. テーマのデータ規模は接頭辞数が100を超えないことを保証し,一次行列乗算は三方的で,全部でlog(n)回乗算する.したがって,この問題の全体的な複雑さは100^3*log(n),ACである. 最後に9番目の問題のコードを提供して参考にします(今日書いたのは、C++のクラスと演算子のリロードを熟知しています).コードを見ているうちに忘れてしまうのを避けるために、私はこの言葉を前に置いて言いました. Matrix 67オリジナル、転載は出典を明記してください.
#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;
class CMatrix
{
public:
long element[MAX_SIZE][MAX_SIZE];
void setSize(int);
void setModulo(int);
CMatrix operator* (CMatrix);
CMatrix power(int);
private:
int size;
long modulo;
};
void CMatrix::setSize(int a)
{
for (int i=0; i<a; i++)
for (int j=0; j<a; j++)
element[i][j]=0;
size = a;
}
void CMatrix::setModulo(int a)
{
modulo = a;
}
CMatrix CMatrix::operator* (CMatrix param)
{
CMatrix product;
product.setSize(size);
product.setModulo(modulo);
for (int i=0; i<size; i++)
for (int j=0; j<size; j++)
for (int k=0; k<size; k++)
{
product.element[i][j]+=element[i][k]*param.element[k][j];
product.element[i][j]%=modulo;
}
return product;
}
CMatrix CMatrix::power(int exp)
{
CMatrix tmp = (*this) * (*this);
if (exp==1) return *this;
else if (exp & 1) return tmp.power(exp/2) * (*this);
else return tmp.power(exp/2);
}
int main()
{
const int validSet[]={0,3,6,12,15,24,27,30};
long n, m, p;
CMatrix unit;
scanf("%d%d%d", &n, &m, &p);
unit.setSize(SIZE);
for(int i=0; i<SIZE; i++)
for(int j=0; j<SIZE; j++)
if( ((~i)&j) == ((~i)&(SIZE-1)) )
{
bool isValid=false;
for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];
unit.element[i][j]=isValid;
}
unit.setModulo(p);
printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
return 0;
}