NKOJ-3711 擺花<L特供版>

P3711擺花

時間限制 : - MS 空間限制 : 65536 KB

評測說明 : 時限1000ms

問題描述

藝術館門前将擺出許多花，一共有n個位置排成一排，每個位置可以擺花也可以不擺花。有些花如果擺在相鄰的位置（隔着一個空的位置不算相鄰），就不好看了。假定每種花數量無限，求擺花的方案數。
           

輸入格式

輸入共有1+m行：
第一行有兩個用空格隔開的正整數n、m，m表示花的種類數。
接下來的m行，每行有m個字元1或0,若第i行第j列為1，則表示第i種花和第j種花不能排在相鄰的位置，輸入保證對稱。（提示：同一種花可能不能排在相鄰位置）。
           

輸出格式

輸出隻有一個整數，為方案數（這個數字可能很大，請輸出方案數除以1000000007的餘數）
           

樣例輸入 1

2 2
0 1
1 0
           

樣例輸出 1

7
           

樣例輸入 2

3 3
0 0 0 
0 1 0 
0 0 1 
           

樣例輸出 2

50
           

提示

樣例說明
七種方案為(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）
100%的資料，1＜n≤1000000000，0＜m≤100。
           

其實我真的沒有注意到原來藝術館門前的花擺的這麼講究（因為感覺它們都是一個顔色）

題解

先講講動歸（畢竟特供版，還是要打好基礎）

所謂動歸，就是确定某個狀态dp[i]，并探讨i的值不同時dp之間的關系

說白了，就是找規律

但由于動歸的規律一般都不會很直白地告訴你，是以我們一般需要把題目數學抽象化

然後得出類似于

dp[i]=dp[i-1]+dp[i-2]
           

之類的公式（這就是遞推式）（所有資料的通解，并且一般需要遞歸）

遞推式

首先,這道題目用動歸(基本上所有擺成一排的東西都可以用動歸敷衍了事)

然後我們就需要知道動歸的遞推式

由于這邊有很多種花

想要用一個遞推式表達不太可能

因為我們定狀态時需要一個位置一個位置地讨論
是以我們規定dp[i]為擺花擺到第i個位置時地方案數
但由于dp[i]與dp[i-1]之間的關系不是很簡單
比如,第1種花不能和第2種放在一起
那麼遞歸式就應該為
對于第一種花,dp[i]=1*（第一種花的）dp[i-1]+0*dp[i-1]
           

是以我們的遞推式也應該分類進行讨論

首先我們用動歸的思維來進行分析

假設一共隻有兩種花,并且第一種與第二種是不能相鄰的
那麼在某一個空位上就有三種選擇,第一種,第二種,或者不放花

按照動态規劃的思維,我們假設已經知道了前n-1個位置放花的總方案數dp[n-1],求第n個位置放花的方案數dp[n]
那麼,我們必須知道第n-1個位置放的是什麼花
而簡單的dp[n-1]表示的隻是放到第n-1個位置總的方案數,無法得知放的是什麼花
是以我們選擇加一維數組
于是最新的狀态為dp[f][n],表示在第n個位置上放上第f種花的總方案數

現在思考一下
我們如果已知dp[0][n-1],dp[1][n-1],dp[2][n-1]
f=0的時候(也就是不放花),因為不放花與其它兩種沒有沖突,是以我們可以選擇在dp[1][n-1]後不放花,也可以選擇在dp[2][n-1]後不放花,也可以在dp[0][n-1]後不放花
    于是dp[0][n]= 1 *dp[0][n-1]+ 1 *dp[1][n-1]+ 1 *dp[2][n-1]
f=1的時候(放第1種花),根據上述思路,我們不能夠在第2種花後面放第一種花,而其它兩種方案都可行
    于是dp[1][n]= 1 *dp[0][n-1]+ 1 *dp[1][n-1]+ 0 *dp[2][n-1]
f=2的時候(放第2種花),同上
    于是dp[2][n]= 1 *dp[0][n-1]+ 0 *dp[1][n-1]+ 1 *dp[2][n-1]
           

這就是大概的思維過程

是以我們也可以推斷出一個式子

如果已知目前的各種花的最大方案數為dp[0][n-1],dp[1][n-1],dp[2][n-1]...,dp[f][n-1]
那麼對于目前讨論的花k,它前面一格的每種花為i
如果在用can[i]=1表示它可以接在某種花之後,用can[i]=0表示它不可以接在某種花之後
那麼dp[k][n]=can[0]*dp[0][n-1]+can[1]*dp[1][n-1]+...
即can[i]為dp[i][n-1]的系數
           

轉化為矩陣

那麼我們定義矩陣

如果有k種花(第0種為不放花),且目前放到了第n個位置

矩陣狀态為

dp[0][n],dp[1][n]...dp[k][n]
           

由上面的推導可得第二個矩陣的狀态

第k列就應該是第k種花對應的can數組的值(注意此處為列)

結合到上一道3712的系數法來看這道題目
第二個矩陣的第k列其實就對應了dp[k][n]的遞推式的系數
           

關于矩陣

我知道這對于初學者來講确實很難了解,但是方法也是需要了解的，想要搞懂還請多次嘗試了解

并且我确實很難再講得更精細了

這道3711和3712其實都是為初學者寫的(甚至可能沒學過動歸)

因為矩陣舉例子實在是很累,是以我沒有舉太多例子

不過現在了解不到也沒什麼，反正何老闆會講動歸的

動歸轉化成矩陣并不難，難的是動歸本身

我會再更新幾篇關于動歸的題目來加深對遞推式的了解

那麼關于矩陣的構造，詳細過程就此告一段落了

總結下來

對于矩陣1的第一行第k項
矩陣2中的第k列的各個數字對應的就是它的遞推式的系數
           

你學到了麼？？

附上代碼（僅用于對答案）

#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000000007;
using namespace std;

int n,m;

struct trix
{
    long long x[][];
    trix(){memset(x,,sizeof(x));}
    trix operator *(const trix&y)
    {
        trix ans=trix();
        for(int a=;a<=m;a++)
        for(int b=;b<=m;b++)
        for(int c=;c<=m;c++)
            ans.x[a][b]+=(x[a][c]*y.x[c][b])%mod;
        for(int a=;a<=m;a++)
        for(int b=;b<=m;b++)
            ans.x[a][b]=ans.x[a][b]%mod;
        return ans;
    }
    void out()
    {
        long long ans=;
        for(int i=;i<=m;i++)ans=(ans+x[][i])%mod;
        printf("%lld",ans);
    }
};

trix ori=trix(),add=trix();

void multi(int t)//矩陣快速幂
{
    while(t)
    {
        if(t&)ori=ori*add;
        add=add*add;
        t>>=;
    }
    ori.out();
}

int main()
{
    int c;
    scanf("%d%d",&n,&m);
    for(int a=;a<=m;a++)ori.x[][a]=add.x[][a]=add.x[a][]=;
    for(int a=;a<=m;a++)
    for(int b=;b<=m;b++)scanf("%d",&c),add.x[b][a]=-c;//以上三行都在建矩陣
    multi(n-);
}