每日一水第37弹(莫比乌斯反演)

http://acm.hdu.edu.cn/showproblem.php?pid=5219

求不重复的子串的数量,即不能是xxxx的形式。

首先让我们来复习一下莫比乌斯反演。


http://acm.hust.edu.cn/vjudge/contest/view.action?cid=36016#overview
f(n) :某个值(根据题目定义) >= n的数量

 g(n) : 恰好等于n的数量

f(n) = \sum\limits_{d|n}^{}{g(d)} (d%n==0)
反演之后就变成了
g(n) = \sum\limits_{d|n}^{}{mu[d/n]*f(d)} (d%n==0)
特殊的
g(1) = \sum\limits_{d|n}^{}{mu[d]*f(d)} (d%n==0)
mu函数可以这么求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool flag[N];
int p[N],pn,mu[N];
void init()
{
    pn=0;
    mu[1] = 1;
    for(int i = 2; i < N; i++)
    {
        if(!flag[i]) p[pn++] = i, mu[i] = -1;
        for(int j = 0; j < pn && i*p[j] < N; j++)
        {
            flag[i*p[j]] = true;
            if(i%p[j]==0) {
                mu[i*p[j]] = 0;
                break;
            }
            else
                mu[i*p[j]] = -mu[i];
        }
    }
}

现在让我们来尝试着解决上面那个字符串题把

f(n)表示能分成n的倍数份的字符串的总数。即一个字符串substring = xxx...xx (n个x)

同样的,设g(n)表示恰好分成n份的字符串的总数,我们要求的就是g(1)

所以假设我枚举了一份的长度len,比如某个子串是substring = yyyy...yyy (m个y)的形式,y的长度为len,

这个时候f(1) += m, f(2) += (m - 1).... f(m) += 1

这样子的话,我枚举了所有的len,也能达到枚举了所有的子串的目的。

然后通过上面的反演公式我们就可以求出g(1)了。

球的时候暴力求出f数组或者用莫比乌斯的前缀和优化都行,下面是两种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
const int BASE = 1230301;
long long H[N], Pow[N], a[N];
inline long long geth(int L, int R)
{
    return H[R+1] - H[L] * Pow[R - L + 1];
}
int getpre(int pos1, int pos2, int len)
{
    if(pos1 == -1) {
        return 0;
    }
    int left = 1, right = len, best = 0;
    while(left <= right) {
        int mid = (left + right) >> 1;
        if(geth(pos1 - mid + 1, pos1) == geth(pos2 - mid + 1, pos2)) {
            best = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return best;
}
int getsuf(int pos1, int pos2, int len)
{
    int left = 1, right = len, best = 0;
    while(left <= right) {
        int mid = (left + right) >> 1;
        if(geth(pos1, pos1 + mid - 1) == geth(pos2, pos2 + mid - 1)) {
            best = mid ;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return best;
}
bool flag[N];
int p[N],pn,mu[N];
long long summu[N], summui[N];
void init()
{
    pn=0;
    mu[1] = 1;
    for(int i = 2; i < N; i++){
        if(!flag[i]) p[pn++] = i, mu[i] = -1;
        for(int j = 0; j < pn && i*p[j] < N; j++) {
            flag[i*p[j]] = true;
            if(i%p[j]==0) {
                mu[i*p[j]] = 0;
                break;
            }
            else
                mu[i*p[j]] = -mu[i];
        }
    }
    summu[0] = summu[1] = 0;
    summui[0] = summui[1] = 0;
    for(int i = 2; i < N; i++) {
        summu[i] = summu[i - 1] + mu[i];
        summui[i] = summui[i - 1] + mu[i] * i;
    }
}
char s[N];
long long f[N];
#define wuyiqi
int main()
{
    srand(time(NULL));
    init();
    Pow[0] = 1;
    for(int i = 1; i < N; i++) Pow[i] = Pow[i - 1] * BASE;
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        int n = strlen(s);
        for(int i = 0; i < n; i++) {
            s[i + n] = '@';
        }
        H[0] = 0;
        for(int i = 0; i < 2 * n; i++) {
            H[i + 1] = H[i] * BASE + s[i];
        }
        long long ret = 1LL * n * (n + 1) / 2;
        memset(f, 0, sizeof(f));
        f[1] = ret;
        for(int len = 1; len <= n; len++) {
            int m = (n - 1) / len + 1;
            for(int i = 0; i < m; i++) {
                a[i] = geth(i * len, (i + 1) * len - 1);
            }
            for(int i = 0, j = 0; i < m; i = ++j) {
                while(j + 1 < m && a[i] == a[j + 1]) {
                    j++;
                }
                int k = j - i + 1;
                int suf = getsuf(i * len, (i + k) * len, len);
                int pre = getpre(i * len - 1, (i + k) * len - 1, len);
 
                for(int i = 2; i <= k; i++) {
                    f[i] += 1LL * k * len - i * len + 1 + pre + suf;
                }
                if(pre + suf >= len) {
                    f[k + 1] += 1 + pre + suf - len;
                }
            }
        }
        long long res = 0;
        for(int i = 1; i <= n; i++) {
            res += 1LL * f[i] * mu[i];
        }
        printf("%I64d\n", res);
    }
    return 0;
}

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
const int BASE = 111;
const long long MOD = 1e9 + 9;
long long H[N], Pow[N], a[N];
inline long long geth(int L, int R)
{
    return (H[R+1] - H[L] * Pow[R - L + 1] % MOD + MOD) % MOD;
}
int getpre(int pos1, int pos2, int len)
{
    if(pos1 == -1) {
        return 0;
    }
    int left = 1, right = len, best = 0;
    while(left <= right) {
        int mid = (left + right) >> 1;
        if(geth(pos1 - mid + 1, pos1) == geth(pos2 - mid + 1, pos2)) {
            best = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return best;
}
int getsuf(int pos1, int pos2, int len)
{
    int left = 1, right = len, best = 0;
    while(left <= right) {
        int mid = (left + right) >> 1;
        if(geth(pos1, pos1 + mid - 1) == geth(pos2, pos2 + mid - 1)) {
            best = mid ;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return best;
}
bool flag[N];
int p[N],pn,mu[N];
long long summu[N], summui[N];
void init()
{
    pn=0;
    mu[1] = 1;
    for(int i = 2; i < N; i++){
        if(!flag[i]) p[pn++] = i, mu[i] = -1;
        for(int j = 0; j < pn && i*p[j] < N; j++) {
            flag[i*p[j]] = true;
            if(i%p[j]==0) {
                mu[i*p[j]] = 0;
                break;
            }
            else
                mu[i*p[j]] = -mu[i];
        }
    }
    summu[0] = summu[1] = 0;
    summui[0] = summui[1] = 0;
    for(int i = 2; i < N; i++) {
        summu[i] = summu[i - 1] + mu[i];
        summui[i] = summui[i - 1] + mu[i] * i;
    }
}
char s[N];
long long f[N];
int main()
{
    init();
    Pow[0] = 1;
    for(int i = 1; i < N; i++) Pow[i] = Pow[i - 1] * BASE % MOD;
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        int n = strlen(s);
        for(int i = 0; i < n; i++) {
            s[i + n] = '@';
        }
        H[0] = 0;
        for(int i = 0; i < 2 * n; i++) {
            H[i + 1] = (H[i] * BASE % MOD + s[i]) % MOD;
        }
        long long ret = 1LL * n * (n + 1) / 2;
        for(int len = 1; len <= n; len++) {
            int m = (n - 1) / len + 1;
            for(int i = 0; i < m; i++) {
                a[i] = geth(i * len, (i + 1) * len - 1);
            }
            for(int i = 0, j = 0; i < m; i = ++j) {
                while(j + 1 < m && a[i] == a[j + 1]) {
                    j++;
                }
                int k = j - i + 1;
                int suf = getsuf(i * len, (i + k) * len, len);
                int pre = getpre(i * len - 1, (i + k) * len - 1, len);
                ret += summu[k] * (k * len + 1 + pre + suf ) - 1LL * len * summui[k];
                if(pre + suf >= len) {
                    ret += mu[k + 1] * (pre + suf - len + 1);
                }
            }
        }
        printf("%I64d\n", ret);
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注