程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2254 奧運(矩陣)

HDU 2254 奧運(矩陣)

編輯：C++入門知識

HDU 2254 奧運(矩陣)

題目地址：HDU 2254

必須得吐槽一下。。這題的數據是又弱又坑。。樣例不過都能AC。。還有。。居然還有重邊。。WA了一晚上。。

吐槽完畢，言歸正傳。。

根據離散數學裡面的可達矩陣的性質，我們知道一個有向圖的鄰接矩陣的前n次冪的和即為可達矩陣，那麼要求[t1-t2]之內的路徑的條數，因為題目說了t1 = 0的時候為0。那麼假設鄰接矩陣為A，那麼要求的就是A^(t1-1)+A^(t1)+...+A^(t2-1)，為什麼是從t1-1開始呢，因為鄰接矩陣本身代表走一步的結果。

然後再加上離散化就可以做了。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL __int64
const int mod=2008;
int n;
LL q[40];
struct matrix
{
    int ma[32][32];
} mat[10002];
matrix Mult(matrix x, matrix y)
{
    int i, j, k;
    matrix tmp;
    memset(tmp.ma,0,sizeof(tmp.ma));
    for(i=0; i

C++入門知識

編程算法 - 數組中的逆序對代碼(C)

數組中的逆序對代碼(C)

Spork: Pig on Spark實現分析

介紹 Spork是Pig on Spark的highl

C++類靜態數據成員與類靜態成員函數

　　在沒有講述本章內容之前假如我們想要在一個范圍內共

ZOJ 3640 Help Me Escape 概率dp

ZOJ 3640 Help Me Escape 概率dp

hdu 2814 Interesting Fibonacci

hdu 2814 Interesting Fibonacci

輸入N個數，輸出所有可能的排列組合(6+個小時啊，耶稣~)

輸入N個數，輸出所有可能的排列組合