NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2009高中組決賽
 NPSC 2009 高中組 決賽 A. 秦始皇的字典

作者 主題: NPSC 2009 高中組 決賽 A. 秦始皇的字典  (閱讀 2415 次)

MaskRay

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
NPSC 2009 高中組 決賽 A. 秦始皇的字典
« 於: 四月 04, 2010, 09:07:59 pm »

說明:給出一些「反秦」字詞片段,求出所有長度不超過 L 的不出現這些字詞片段的詞彙的數目

解法:構建Aho-Corasick 自動機,標記「反秦」字詞片段代表的狀態以及它們的後代為不可用
構造一個可用狀態轉移矩陣A(M*M 的矩陣),M 是有效的狀態數,無效狀態被剔除了
A_i_j = v 表示狀態j 轉移到狀態i 有v 種方法


使用Russian Peasant Multiplication,那麼做big-omicron(log L) 次矩陣乘法即可得到A^L
A^L 第一列的數累加就得到了長度為L 的有效詞條數目


根據題意,我們需要知道ANS = A + A^2 + A^3 + …… + A^L,ANS 第一列累加就是題目要求的答案
這又是一個經典技巧,構造2M * 2M 的矩陣 B
A I
0 I
I 為單位矩陣,0 為零矩陣
B^(L+1) 右上角的M*M 矩陣就等於A^0 + A^1 + …… + A^L,容易計算出ANS


時間複雜度:big-omiron(M^3 * log L),構造Aho-Corasick 自動機的複雜度是線性的,可省略
瓶頸在於矩陣乘法,我們可以採用一些高級的矩陣乘法演算法。我的程式沒有採用,在我的機器上跑了18 秒

代碼: [選擇]
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long i64;

const int V = 146, MOD = 10000019;
struct Node
{
    Node *ch[26], *pi;
    bool flag;
    Node() : flag(false) {memset(ch, 0, sizeof(ch)); }
    void *operator new(size_t, void *p) {return p; }
} pool[V], *pit, *q[V];

void insert(const char *s)
{
    Node *x = pool;
    for (; *s; s++) {
        if (!x->ch[*s-'a']) x->ch[*s-'a'] = new(pit++) Node;
        x = x->ch[*s-'a'];
        if (x->flag) return;
    }
    x->flag = true;
}

void aho_corasick()
{
    int fore = 0, rear = 0;
    for (int i = 0; i < 26; i++)
        if (!pool->ch[i]) pool->ch[i] = pool;
        else pool->ch[i]->pi = pool, q[rear++] = pool->ch[i];
    while (fore < rear) {
        Node *u = q[fore++];
        if (u->pi->flag) u->flag = true;
        if (u->flag) continue;
        for (int i = 0; i < 26; i++)
            if (!u->ch[i]) u->ch[i] = u->pi->ch[i];
            else u->ch[i]->pi = u->pi->ch[i], q[rear++] = u->ch[i];
    }
}

struct Matrix
{
    int m, n;
    int a[V*2][V*2];
    Matrix(int m, int n) : m(m), n(n) {memset(a, 0, sizeof(a)); }
    int &operator()(int i, int j) {return a[i][j]; }
    Matrix operator*(const Matrix &rhs) {
        Matrix ret(m, rhs.n);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < rhs.n; j++) {
                i64 t = 0;
                for (int k = 0; k < n; k++)
                    t = t+(i64)a[i][k]*rhs.a[k][j];
                ret(i, j) = t%MOD;
            }
        return ret;
    }
};

int main()
{
    char s[21];
    int cases, n, L;
    for (scanf("%d", &cases); cases--; ) {
        pit = pool+1;
        new(pool) Node;
        scanf("%d%d", &n, &L);
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            insert(s);
        }

        int id = pit-pool;
        Matrix A(id*2, id*2);
        aho_corasick();
        for (Node *it = pool; it != pit; it++)
            if (!it->flag)
                for (int i = 0; i < 26; i++)
                    if (it->ch[i] && !it->ch[i]->flag)
                        A(it->ch[i]-pool, it-pool) ++;
        for (int i = 0; i < id; i++)
            A(i, id+i) = A(id+i, id+i) = 1;

        Matrix B(id*2, id*2);
        for (int i = 0; i < id*2; i++)
            B(i, i) = 1;
        for (L++; L; L >>= 1, A = A*A)
            if (L & 1)
                B = A*B;

        int ans = -1;
        for (Node *it = pool; it != pit; it++)
            if (!it->flag)
                ans = (ans + B(it-pool, id) + MOD) % MOD;
        printf("%d\n", ans);
    }
}
記錄

ck99126

  • 新手
  • *
  • 文章數: 6
    • 檢視個人資料
Re: NPSC 2009 高中組 決賽 A. 秦始皇的字典
« 回覆 #1 於: 四月 13, 2013, 09:18:45 pm »

其實這題在矩陣乘法的部分不需要任何高級的算法,
只需要做點特別的常數優化。

接MaskRay的文章
觀察B的冪次:

A I
O I

A2 A+I
O     I

A3 A2+A+I
O     I

A4 A3+A2+A+I
O     I

就是底下那兩塊永遠動不到,那就別碰。
再來,碰到O的不要乘,碰到I的直接加。
我個人做到3.3s
« 上次編輯: 四月 28, 2014, 07:45:07 am 由 ck99126 »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2009高中組決賽
 NPSC 2009 高中組 決賽 A. 秦始皇的字典