KMP

KMP专题(三)

Posted on

专题链接

HDU 3336 Count the string

题意:
事先说好,这题数据非常弱,典型的想的比出的简单,各种错误代码都能A。

这道题的题意是让你找出所有前缀在整个字符串中的子串数量。

思路:
这里只提供所谓出题人的思路,水水过去就算了啊。

对于一个位置,如果他的next数组不是0,说明这个后缀与前缀有匹配。注意这里是后缀,而不是在整个字符串范围内。然而这个思路还是A了。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary));

const int maxn = 2e5 + 5;
const int mod = 10007;

char des[maxn];
int nxt[maxn];
int len;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < len)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %s", &len, des);
        getNext();
        int ans = len;
        range(i, 1, len) if (nxt[i]) ans = (ans + 1) % mod;
        printf("%d\n", ans);
    }
    return 0;
}

HDU 4300 Clairewd’s message

题意:
还是还是还是还是还是还还是还是求最长相同前后缀的题。

思路:
无。

AC Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e5 + 5;

char des[maxn], table[30], retable[30];
int nxt[maxn], len;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = strlen(des);
    while (i < len) {
        if (j == -1 || table[des[i] - 'a'] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %s", table, des);
        each(i, 26) retable[table[i] - 'a'] = 'a' + i;
        getNext();
        int crylen = len - nxt[len];
        crylen = crylen < (len + 1) / 2 ? (len + 1) / 2 : crylen;
        each(i, crylen) putchar(des[i]);
        each(i, crylen) putchar(retable[des[i] - 'a']);
        puts("");
    }
    return 0;
}

HDU 1238 Substrings

题意:
找出一个最长的字符串,使得它或他的反转是每个给定字符串的连续字串。

思路:
暴力枚举。

AC Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int inf = 0x3f3f3f3f;
const int maxn = 1e2 + 5;

int nxt[maxn], len;
char mat[maxn][maxn], des[maxn];

void getNext(const string& des)
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = des.length();
    while (i < len) {
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

bool kmpMatch(const char* src, const string& des)
{
    int i = 0, j = 0, slen = strlen(src), dlen = des.length();
    getNext(des);
    while (i < slen && j < dlen) {
        if (j == -1 || src[i] == des[j])
            i++, j++;
        else
            j = nxt[j];
    }
    return j == dlen;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int min_len = inf, max_len = 0;
        each(i, n) scanf("%s", mat[i]), min_len = min(min_len, (int)strlen(mat[i]));
        range(l, 1, min_len) range(s, 0, min_len - l)
        {
            string tmp = "", rtmp;
            range(i, s, s + l - 1) tmp += mat[0][i];
            rtmp = string(tmp.rbegin(), tmp.rend());
            bool flag = true;
            range(i, 1, n - 1) if (!kmpMatch(mat[i], tmp) && !kmpMatch(mat[i], rtmp))
            {
                flag = false;
                break;
            }
            if (flag)
                max_len = l;
        }
        printf("%d\n", max_len);
    }
    return 0;
}

HDU 2328 Corporate Identity

题意:
还是找出最长的公共连续子串。

思路:
暴力枚举。

AC Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int inf = 0x3f3f3f3f;
const int maxn = 2e2 + 5;

int nxt[maxn], len;
char mat[4010][maxn], des[maxn];

void getNext(const string& des)
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = des.length();
    while (i < len) {
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

bool kmpMatch(const char* src, const string& des)
{
    int i = 0, j = 0, slen = strlen(src), dlen = des.length();
    getNext(des);
    while (i < slen && j < dlen) {
        if (j == -1 || src[i] == des[j])
            i++, j++;
        else
            j = nxt[j];
    }
    return j == dlen;
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n) {
        int min_len = inf;
        string ans = "";
        each(i, n) scanf("%s", mat[i]), min_len = min(min_len, (int)strlen(mat[i]));
        range(l, 1, min_len) range(s, 0, min_len - l)
        {
            string tmp = "";
            range(i, s, s + l - 1) tmp += mat[0][i];
            if (ans.length() == tmp.length() && ans < tmp)
                continue;
            bool flag = true;
            range(i, 1, n - 1) if (!kmpMatch(mat[i], tmp))
            {
                flag = false;
                break;
            }
            if (flag)
                ans = tmp;
        }
        if (ans.length() == 0)
            puts("IDENTITY LOST");
        else
            cout << ans << endl;
    }
    return 0;
}

小结

简单说一下,KMP可以解决的问题。

  • 较高效的字符串匹配
  • 较高效的字符串匹配计数
  • 找最短循环节
  • 找最长相同前后缀
  • 累积的相同前后缀记录

主要是理解了next数组,一切好说。

KMP

KMP专题(二)

Posted on

专题链接

KMP专题(一)
KMP专题(三)

HUST 1010 The Minimum Length

题意:
找最小循环节长度。

思路:
无。

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
int len, nxt[maxn];
char des[maxn];

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < len) {
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
    }
}

int main()
{
    while (scanf("%s", des) != EOF) {
        len = strlen(des);
        getNext();
        printf("%d\n", len - nxt[len]);
    }
    return 0;
}

POJ 2406 Power Strings

题意:
找最短循环节……

思路:
无。

#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
char src[maxn], des[maxn];
int slen, tlen;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < tlen)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    while (scanf("%s", des) != EOF) {
        if (des[0] == '.' && des[1] == '\0')
            break;
        tlen = strlen(des);
        getNext();
        int len = tlen - nxt[tlen];
        if (tlen % len == 0)
            printf("%d\n", tlen / len);
        else
            puts("1");
    }
    return 0;
}

POJ 2752 Seek the Name, Seek the Fame

题意:
计算所有 前缀和后缀相同的字符串。

思路:
有点意思。这道题需要对 next 数组更深一层的了解。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

typedef long long ll;

const int maxn = 4e5 + 10;
char str[maxn];
int nxt[maxn], ans[maxn];
int len, num;

void getNext()
{
    num = 0;
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < len)
        if (j == -1 || str[i] == str[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    while (scanf("%s", str) != EOF) {
        len = strlen(str);
        getNext();
        while (len > 0) {
            ans[num++] = len;
            len = nxt[len];
        }
        rrange(i, 0, num - 1) printf("%d%c", ans[i], i ? ' ' : '\n');
    }
    return 0;
}

POJ 3080 Blue Jeans

题意:
给出多个字符串,找出最长的且字典序最小的公共连续子串。

思路:
数据很小,直接枚举第一个字符串的所有连续子串,再对其他 n-1 个字符串尝试匹配即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

const int maxn = 65;
char mat[15][maxn];
int nxt[maxn];

void getNext(const string& str)
{
    int len = str.length(), i = 0, j = -1;
    nxt[0] = -1;
    while (i < len)
        if (j == -1 || str[i] == str[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

bool kmpIndex(const char* src, const string& des)
{
    int i = 0, j = 0, len = des.length();
    getNext(des);
    while (i < 60 && j < len)
        if (j == -1 || src[i] == des[j])
            i++, j++;
        else
            j = nxt[j];
    return j == len;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        each(i, n) scanf("%s", mat[i]);
        string ans = "";
        range(l, 3, 60) range(s, 0, 60 - l)
        {
            string tmp = "";
            range(i, s, s + l - 1) tmp += mat[0][i];
            if (tmp.length() == ans.length() && tmp > ans)
                continue;
            bool flag = true;
            range(i, 1, n - 1) if (!kmpIndex(mat[i], tmp))
            {
                flag = false;
                break;
            }
            if (flag)
                ans = tmp;
        }
        if (ans.length() == 0)
            puts("no significant commonalities");
        else
            cout << ans << endl;
    }
    return 0;
}

HDU 2594 Simpsons’ Hidden Talents

题意:
给出两个字符串,找出最长的前缀与后缀相同的子串。

思路:
还是老思路,只要把两个字符串连接起来就可以了。但是有一个问题,就是匹配的时候可能会越界。
比如说 abab 与 ab 如果是直接连接起来,那么算法给出的结果将会是 ababab 。
一个行之有效的方法就是在中间加一个不会出现的字符,比如说 ' # ' ,' & ' ,加上以后只有当两个字符串相同的才会出现越界情况。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

const int maxn = 5e4 + 5;

char s[maxn], des[maxn * 2];
int nxt[maxn * 2], len;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    len = strlen(des);
    while (i < len)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    while (scanf("%s", des) != EOF) {
        scanf("%s", s);
        strcat(des, "#");
        strcat(des, s);
        getNext();
        int ans = nxt[len];
        each(i, ans) putchar(des[i]);
        if (ans)
            putchar(' ');
        printf("%d\n", ans);
    }
    return 0;
}
KMP

KMP专题(一)

Posted on

前言

OK,刷专题终于刷到了自己不会的最小表示法,在学习最小表示法之前,稍微总结一下。

kmp多水题,而且因为挂在hdu和poj上,本身有些数据也非常水,所以打算开个专题来汇总一下这些水题。

KMP专题链接

题解

HDU 1711 Number Sequence

题意:
返回第一个数字序列匹配的位置。

思路:
KMP入门题。

AC Code

#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
int src[maxn], des[maxn];
int slen, tlen;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < tlen)
        if (j == -1 || des[i] == des[j]) {
            if (des[++i] != des[++j])
                nxt[i] = j;
            else
                nxt[i] = nxt[j];
        } else
            j = nxt[j];
}

int KMPIndex()
{
    int i = 0, j = 0;
    getNext();
    while (i < slen && j < tlen)
        if (j == -1 || src[i] == des[j]) {
            i++;
            j++;
        } else
            j = nxt[j];
    if (j == tlen)
        return i - tlen + 1;
    else
        return -1;
}

int main()
{
    int T_T;
    scanf("%d", &T_T);
    while (T_T--) {
        scanf("%d %d", &slen, &tlen);
        each(i, slen)
            scanf("%d", src + i);
        each(i, tlen)
            scanf("%d", des + i);
        printf("%d\n", KMPIndex());
    }
    return 0;
}

HDU 1686 Oulipo

题意:
返回匹配数量。

思路
KMP入门题。

AC Code

#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
char src[maxn], des[maxn];
int slen, tlen;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < tlen)
        if (j == -1 || des[i] == des[j]) {
            if (des[++i] != des[++j])
                nxt[i] = j;
            else
                nxt[i] = nxt[j];
        } else
            j = nxt[j];
}

int KMPCount()
{
    int i, j = 0, ans = 0;
    if (slen == 1 && tlen == 1) {
        if (src[0] == des[0])
            return 1;
        else
            return 0;
    }
    getNext();
    for (i = 0; i < slen; i++) {
        while (j > 0 && src[i] != des[j])
            j = nxt[j];
        if (src[i] == des[j])
            j++;
        if (j == tlen) {
            ans++;
            j = nxt[j];
        }
    }
    return ans;
}

int main()
{
    int T_T;
    scanf("%d", &T_T);
    while (T_T--) {
        scanf("%s", des);
        scanf("%s", src);
        slen = strlen(src);
        tlen = strlen(des);
        printf("%d\n", KMPCount());
    }
    return 0;
}

HDU 2087 剪花布条

题意:
返回匹配数量,有点不一样的地方就是不能有重叠。比如说 aaaa 只能计作 两个 aa。

思路:
模板改一个小地方就好了。

AC Code

#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
char src[maxn], des[maxn];
int slen, tlen;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < tlen)
        if (j == -1 || des[i] == des[j]) {
            if (des[++i] != des[++j])
                nxt[i] = j;
            else
                nxt[i] = nxt[j];
        } else
            j = nxt[j];
}

int KMPCount()
{
    int i, j = 0, ans = 0;
    getNext();
    for (i = 0; i < slen; i++) {
        while (j > 0 && src[i] != des[j])
            j = nxt[j];
        if (src[i] == des[j])
            j++;
        if (j == tlen) {
            ans++;
            j = 0;
            //j = nxt[j];
        }
    }
    return ans;
}

int main()
{
    while (scanf("%s", src)) {
        if (src[0] == '#' && src[1] == '\0')
            break;
        scanf("%s", des);
        slen = strlen(src);
        tlen = strlen(des);
        printf("%d\n", KMPCount());
    }
    return 0;
}

HDU 3746 Cyclic Nacklace

当时第一次发现kmp的next数组的应用,简直惊为天人,立马写了一片博客……认为,恩,好题!

事实上这类题目,巨tm多……
博文链接

HDU 1358 Period

题意:
题目什么意思来着……

再看了一下题目,原来还是求循环节……对于每个位置都找一下循环节,如果刚好是完整的几个循环节而来,就输出这个位置和循环次数。

思路:
上面那篇懂了得话,这题也是水题。

AC Code

#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
char src[maxn], des[maxn];
int slen, tlen;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < tlen)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    int cas = 0;
    while (scanf("%d", &tlen) && tlen) {
        scanf("%s", des);
        getNext();
        printf("Test case #%d\n", ++cas);
        for (int i = 2; i <= tlen; i++) {
            int len = i - nxt[i];
            if (i != len && i % len == 0)
                printf("%d %d\n", i, i / len);
        }
        puts("");
    }
    return 0;
}
Cayley

BZOJ 4766 文艺计算姬

Posted on

完全二分图的生成树计数问题。

这里是作为找规律的题目出现的……
对于这张图的一边 n 个节点,另一边 m 个节点。 其结果为

$$n^{m-1} \times m^{n-1}$$

因为数据非常大,为 1e18 ,long long 也会爆炸
用到了快速乘,快速幂

题意:
计算完全二分图的生成树数量

思路:
公式已给。证明无。
……

AC Code

#include <cstdio>

using namespace std;
typedef unsigned long long ull;

ull fastMul(ull a, ull b, ull mod)
{
    ull ret = 0;
    for (; a; a >>= 1, b = (b + b) % mod)
        if (a & 1)
            ret = (ret + b) % mod;
    return ret;
}

ull fastPow(ull x, ull a, ull mod)
{
    ull ret = 1;
    for (; a; a >>= 1, x = fastMul(x, x, mod))
        if (a & 1)
            ret = fastMul(ret, x, mod);
    return ret;
}
int main()
{
    ull n, m, p;
    scanf("%lld %lld %lld", &n, &m, &p);
    printf("%lld\n", fastMul(fastPow(n, m - 1, p), fastPow(m, n - 1, p), p));
    return 0;
}
Cayley

BZOJ 1430 小猴打架

Posted on

在搜最小生成树计数的题目的时候不小心发现了一个有趣的东西

51nod 1601

完全图的最小生成树计数问题……题解说需要01字典树,不是很会,先放一放
然后就找到了这个资料 Prüfer编码与Cayley公式

简单说完全图的生成树数量为 \( n^{n-2} \)
这个运用矩阵树也可以计算的

题意:
n只猴子打架,两只猴子打架后就会成为好朋友,就不会打架,朋友关系可传递,问打架的序列方案数。

思路:
n个点的生成树数量为 \( n^{n-2} \) ,顺序为 (n-1)!

AC Code

#include <cstdio>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
const int mod = 9999991;
int n;
long long ans = 1;
int main()
{
    scanf("%d", &n);
    range(i, 1, n - 2) ans = ans * n % mod;
    range(i, 1, n - 1) ans = ans * i % mod;
    printf("%lld", ans);
    return 0;
}

最小生成树

HDU 4408 Minimum Spanning Tree

Posted on

真是不容易啊……
最小生成树计数,虽然说觉得以后已经基本不会考到了,但毕竟防范与未然
具体算法我已经在之前一篇算法证明上提到过了,这里是他的矩阵树实现。

这里的代码就暂时作为我的模板了,之后再找题验证一下。

题意:
最小生成树计数裸题

思路:
详见之前一篇证明文章

这里有个地方我一开始不是很明白,就是为什么要用两个并查集来维护。

纸上画了一画,稍微有点理解,简单说就是为了相同边权的边进行缩点,后续的并查集操作就用缩点后的点集,这符合算法的流程和原理。

该代码已经尝试在BZOJ 1016 上 1A ,作为本人模板使用

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

typedef long long ll;
const int maxn = 105;
const int maxm = 1005;
ll mod, ans;
int n, m;

vector<int> G[maxn];
int root[maxn], vis[maxn], scc[maxn];
int g[maxn][maxn];
ll mat[maxn][maxn];

struct node {
    int u, v, w;
} edges[maxm];

void init()
{
    ans = 1;
    each(i, n + 1) scc[i] = root[i] = i;
    memset(g, 0, sizeof g);
}

int findRoot(int x, int rootAry[])
{
    return rootAry[x] == x ? x : rootAry[x] = findRoot(root[x], rootAry);
}

ll getDet(ll a[][maxn], int n)
{
    range(i, 1, n) range(j, 1, n) a[i][j] = (a[i][j] + mod) % mod;
    ll ret = 1;
    range(i, 1, n - 1)
    {
        range(j, i + 1, n - 1) while (a[j][i])
        {
            ll t = a[i][i] / a[j][i];
            range(k, i, n - 1) a[i][k] = (a[i][k] - a[j][k] * t % mod + mod) % mod;
            swap(a[i], a[j]);
            ret = -ret;
        }
        if (a[i][i] == 0)
            return 0;
        ret = ret * a[i][i] % mod;
    }
    return (ret + mod) % mod;
}

void matrixTree()
{
    range(i, 1, n) if (vis[i])
    {
        G[findRoot(i, root)].push_back(i);
        vis[i] = false;
    }
    range(i, 1, n) if (G[i].size() > 1)
    {
        int sz = G[i].size();
        memset(mat, 0, sizeof mat);
        each(j, sz) range(k, j + 1, sz - 1)
        {
            int u = G[i][j], v = G[i][k];
            if (g[u][v]) {
                mat[k][j] = (mat[j][k] -= g[u][v]);
                mat[k][k] += g[u][v];
                mat[j][j] += g[u][v];
            }
        }
        ans = ans * getDet(mat, G[i].size()) % mod;
        each(j, sz) scc[G[i][j]] = i;
    }
    range(i, 1, n)
    {
        G[i].clear();
        root[i] = scc[i] = findRoot(i, scc);
    }
}

void output()
{
    range(i, 1, n - 1) if (scc[i] != scc[i + 1])
    {
        puts("0");
        return;
    }
    printf("%lld\n", ans % mod);
}

int main()
{
    while (scanf("%d %d %lld", &n, &m, &mod) != EOF && n + m + mod) {
        each(i, m) scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
        sort(edges, edges + m, [](const node& a, const node& b) { return a.w < b.w; });
        init();
        edges[m].w = -1;
        range(i, 0, m)
        {
            if (i && edges[i].w != edges[i - 1].w)
                matrixTree();
            int u = findRoot(edges[i].u, scc), v = findRoot(edges[i].v, scc); //缩点后的点
            if (u != v) {
                vis[u] = vis[v] = true;
                root[findRoot(u, root)] = findRoot(v, root);
                g[u][v]++, g[v][u]++; 
            }
        }
        output();
    }
    return 0;
}