矩陣快速冪的模板

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<string.h>
#define LL long long 
#define mod 1000
using namespace std;
struct mat
{
    int m[105][105];
}unit;

int n,m;
void init_unit()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j)
            {
                unit.m[i][j] = 1;
            }
        }
    }
 } 
 
mat operator * (mat a, mat b)
{
    mat ret;
    LL x;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            x = 0;
            for(int k=0;k<n;k++)
            {
                x += ((LL)a.m[i][k] * b.m[k][j])%mod;
                ret.m[i][j] = x%mod;
            }
        }
    }
    return ret;
}
mat pow_mat(mat a, LL x)
{
    mat ret = unit;
    while(x)
    {
        if(x & 1) ret = ret*a;
        a = a*a;
        x >>= 1;
    }
    return ret;
}
void print(mat tmp)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%d  ",tmp.m[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&m==0) break;
        init_unit();
        mat am;
        memset(am.m,0,sizeof(am.m));
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            am.m[a][b] = 1;
        }
        //print(am);
        int t;
        scanf("%d",&t);
        for(int i=0;i<t;i++)
        {
            int a,b,k;
            scanf("%d%d%d",&a,&b,&k);
            mat tmp = pow_mat(am,k);
            //print(tmp);
            printf("%d\n",tmp.m[a][b]);
        }
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末苍姜，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子悬包，更是在濱河造成了極大的恐慌衙猪，老刑警劉巖，帶你破解...
    沈念sama閱讀 211,376評(píng)論 6贊 491
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件布近，死亡現(xiàn)場(chǎng)離奇詭異垫释，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)吊输，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,126評(píng)論 2贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門饶号，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)铁追，“玉大人季蚂，你說(shuō)我怎么就攤上這事。” “怎么了扭屁？”我有些...
    開(kāi)封第一講書人閱讀 156,966評(píng)論 0贊 347
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵算谈，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我料滥，道長(zhǎng)然眼，這世上最難降的妖魔是什么？ 我笑而不...
    開(kāi)封第一講書人閱讀 56,432評(píng)論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任葵腹，我火速辦了婚禮高每，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘践宴。我一直安慰自己鲸匿，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,519評(píng)論 6贊 385
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布阻肩。 她就那樣靜靜地躺著带欢，像睡著了一般。 火紅的嫁衣襯著肌膚如雪烤惊。 梳的紋絲不亂的頭發(fā)上乔煞，一...
    開(kāi)封第一講書人閱讀 49,792評(píng)論 1贊 290
  • 城市分裂傳說(shuō)
    那天，我揣著相機(jī)與錄音柒室，去河邊找鬼渡贾。 笑死，一個(gè)胖子當(dāng)著我的面吹牛雄右，可吹牛的內(nèi)容都是我干的剥啤。 我是一名探鬼主播，決...
    沈念sama閱讀 38,933評(píng)論 3贊 406
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼不脯，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼府怯！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起防楷，我...
    開(kāi)封第一講書人閱讀 37,701評(píng)論 0贊 266
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤牺丙，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后复局，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體冲簿，經(jīng)...
    沈念sama閱讀 44,143評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,488評(píng)論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年亿昏，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了峦剔。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,626評(píng)論 1贊 340
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡角钩，死狀恐怖吝沫，靈堂內(nèi)的尸體忽然破棺而出呻澜，到底是詐尸還是另有隱情，我是刑警寧澤惨险，帶...
    沈念sama閱讀 34,292評(píng)論 4贊 329
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布羹幸，位于F島的核電站，受9級(jí)特大地震影響辫愉，放射性物質(zhì)發(fā)生泄漏栅受。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,896評(píng)論 3贊 313
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一恭朗、第九天 我趴在偏房一處隱蔽的房頂上張望屏镊。 院中可真熱鬧，春花似錦痰腮、人聲如沸闸衫。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 30,742評(píng)論 0贊 21
  • 一樁弒父案诽嘉，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)蔚出。三九已至，卻和暖如春虫腋，著一層夾襖步出監(jiān)牢的瞬間骄酗，已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 31,977評(píng)論 1贊 265
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工悦冀， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留趋翻，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,324評(píng)論 2贊 360
  • 代替公主和親
    正文 我出身青樓盒蟆，卻偏偏與公主長(zhǎng)得像踏烙，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子历等，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,494評(píng)論 2贊 348

推薦閱讀更多精彩內(nèi)容