A. 该出奇兵了

$tarjan \(割点板子题，处理完割点以后\)dfs$ 求出每个点被删掉以后对答案的最小贡献

code:

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
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>

#define int __int128

using namespace std;

const int N = 100010;

int n, m;
int a[N];
vector<int> h[N];
int dfn[N], low[N], tot;
bool cut[N];
int f[N], g[N], son[N];
int scc[N], cnt;
int stk[N], top;
vector<int> s;

void read(int &n)
{
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    n = x * f;
}

void print(int n)
{
    if(n < 0)
    {
        putchar('-');
        n *= -1;
    }
    if(n > 9) print(n / 10);
    putchar(n % 10 + '0');
}

void tarjan(int u, int root, int father)
{
    int child = 0;
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    for (int i = 0; i < h[u].size(); i++)
    {
        int j = h[u][i];
        if (!dfn[j])
        {
            tarjan(j, root, u);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) 
            {
            	child++;
            	if (u != root || child > 1) cut[u] = true;
            }
        }
        else if (j != father) low[u] = min(low[u], dfn[j]);
    }
    
    if (low[u] == dfn[u])
    {
    	cnt++;
    	int v;
    	do
    	{
    	    v = stk[top--];
    	    scc[v] = cnt;
    	}while (u != v);
    }
}

void dfs(int u)
{
    f[u] = son[u] = a[u];
    s.push_back(u);
    for (int i = 0; i < h[u].size(); i++)
    {
    	int j = h[u][i];
    	if (f[j]) continue;
    	dfs(j);
    	f[u] += f[j];
    	if (cut[u] && scc[u] != scc[j])
    	{
    	    son[u] += f[j];
    	    g[u] += f[j] * f[j];
    	}
    }
}

signed main()
{
    read(n), read(m);
    while (m--)
    {
        int a, b;
        read(a), read(b);
        h[a].push_back(b), h[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) read(a[i]);
    
    int res = 0, minv = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i]) 
        {
            s.clear();
            tarjan(i, i, 0);
            dfs(i);
            res += f[i] * f[i];
            for (int j = 0; j < s.size(); j++)
            {
            	if (cut[s[j]]) g[s[j]] += (f[i] - son[s[j]]) * (f[i] - son[s[j]]);
            	else g[s[j]] = (f[i] - a[s[j]]) * (f[i] - a[s[j]]);
            	minv = min(minv, g[s[j]] - f[i] * f[i]);
            }
        }
    }
    
    print(res + minv);
    
    return 0;
}

B. 小雷的神奇电脑

从 \(m - 1\) 位遍历到第0位，每一位都开两个 \(vector\) ，一个存当前位为 \(0\) 的数，一个存当前位为 \(1\) 的数，并且数组中的元素从 \(m - 1\) 为到当前位的值都相同，最多需要开 \(2^{\log n}\) 个 \(vector\)，用 \(dfs\) 比较好维护。

code:

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200010;

int n, m;
int a[N];

int cal(int a, int b)
{
    int res = 0;
    for (int i = m - 1; i >= 0; i--)
    {
        int x = a >> i & 1, y = b >> i & 1;
        if (x == y) res += (1 << i);
    }
    return res;
}

int dfs(int u, vector<int> s)
{
    if (s.size() == 2) return cal(s[0], s[1]);
    if (s.size() < 2) return 0;
    if (u == -1) return cal(s[0], s[1]);
    
    vector<int> s1, s2;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] >> u & 1) s1.push_back(s[i]);
        else s2.push_back(s[i]);
    }
    
    return max(dfs(u - 1, s1), dfs(u - 1, s2));
}

signed main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> s;
    for (int i = 0; i < n; i++) s.push_back(a[i]);
    
    cout << dfs(m - 1, s) << endl;
    
    return 0;
}

C. 岗位分配

组合数学隔板法，假设剩下\(k\)人没有被分配岗位，则总方案数为

\((1 + \sum_{i=0}^{k-1} \sum_{j=0}^{\min(i, n-1)} \left( C(i, j) \times C(n, j + 1) \right) )\mod \text{MOD}\)

code:

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2010, mod = 998244353;

int n, m;
int f[N], g[N];

int qmi(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void init()
{
    f[0] = g[0] = 1;
    for (int i = 1; i < N; i++)
    {
        f[i] = f[i - 1] * i % mod;
        g[i] = g[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int C(int a, int b)
{
    if (a < b) return 0;
    return f[a] * g[b] % mod * g[a - b] % mod;
}

signed main()
{
    init();
    
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        m -= x;
    }

    int res = 1;
    for (int i = m - 1; i >= 0; i--)
        for (int j = min(i, n - 1); j >= 0; j--)
            res = (res + C(i, j) * C(n, j + 1) % mod) % mod;
    
    cout << res << endl;
    
    return 0;
}

D. 简单的素数

试除法判断质数

code:

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
#include <bits/stdc++.h>

using namespace std;

int T;
int n;

bool check(int x)
{
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        if (check(n)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    
    return 0;
}

E. AND

线性筛质数，可发现只有区间包含 \(2\) 时，\(AND\) 和结果才可能为 \(0\)

code:

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
#include <bits/stdc++.h>

using namespace std;

const int N = 100000010;

int T;
int a, b;
vector<int> p;
int cnt;
bool st[N];

void init()
{
    for (int i = 2; i <= 100000000; i++)
    {
        if(!st[i]) p.push_back(i);
        for (int j = 0; j < p.size(); j++)
        {
            if (p[j] > 100000000 / i) break;
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}

int main()
{
    init();
    
    cin >> T;
    while (T--)
    {
        int x, y;
        cin >> x >> y;
        
        int l = 0, r = p.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (p[mid] < x) l = mid + 1;
            else r = mid;
        }
        int bg = l;
        
        l = 0, r = p.size() - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (p[mid] <= y) l = mid;
            else r = mid - 1;
        }
        int ed = l;
        
        if (p[bg] < x || p[ed] > y) cout << "0 0" << endl;
        else
        {
        	cout << ed - bg + 1 << ' ';
        	if (x > 2 || ed == bg) cout << 0 << endl;
            else cout << ed - bg - 1 << endl;
        }
    }
    
    return 0;
}

F. 小雷的算式

简单模拟，排序后输出

code:

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
#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;
    
    int res = 0;
    vector<int> r;
    for (int i = 0; i < s.size(); i++)
        if (s[i] >= '0' && s[i] <= '9')
        {
            int x = 0;
            for (int j = i; j < s.size(); j++)
            {
                if (s[j] >= '0' && s[j] <= '9') x = x * 10 + s[j] - '0';
                if (s[j] == '+' || j == s.size() - 1)
                {
                    r.push_back(x);
                    res += x;
                    i = j - 1;
                    if (s[j] >= '0' && s[j] <= '9') i++;
                    break;
                }
            }
        }
    
    sort(r.begin(), r.end());
    reverse(r.begin(), r.end());
    
    for (int i = 0; i < r.size(); i++)
    {
        if (i) cout << "+";
        cout << r[i];
    }
    cout << endl;
    
    cout << res << endl;
    
    return 0;
}

G. 循环字符串

用线段树维护正反哈希区间，当 \(hash(l + x, r) == hash(l, r - x)\) 时，\(x\) 为该区间的一个循环节，每个区间最大循环节为区间长度$ len$，试除枚举 \(len\) 的因子，找到最小循环节

code:

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>

#define ls u << 1
#define rs u << 1 | 1

using namespace std;

typedef unsigned long long ull;

const int N = 200010, P = 13331;

int n, m;
string s;
ull p[N], f[N];
int prime[N], minp[N], cnt;
struct Node
{
    int l, r;
    ull lh, rh, lz;
}tr[N * 4];

void pushup(int u)
{
    tr[u].lh = tr[ls].lh * p[tr[rs].r - tr[rs].l + 1] + tr[rs].lh;
    tr[u].rh = tr[rs].rh * p[tr[ls].r - tr[ls].l + 1] + tr[ls].rh;
}

void pushdown(int u)
{
    if (!tr[u].lz) return;
    tr[ls].lh = tr[ls].rh = tr[u].lz * f[tr[ls].r - tr[ls].l];
    tr[rs].lh = tr[rs].rh = tr[u].lz * f[tr[rs].r - tr[rs].l];
    tr[ls].lz = tr[rs].lz = tr[u].lz;
    tr[u].lz = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, (ull)s[l - 1], (ull)s[l - 1]};
    else 
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int c)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
    	tr[u].lh = tr[u].rh = c * f[tr[u].r - tr[u].l];
    	tr[u].lz = c;
    }
    else
    {
    	pushdown(u);
    	int mid = tr[u].l + tr[u].r >> 1;
    	if (l <= mid) modify(ls, l, r, c);
    	if (r > mid) modify(rs, l, r, c);
    	pushup(u);
    }
}

ull query(int u, int l, int r, int st)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
    	if (st == 1) return tr[u].lh * p[r - tr[u].r + 1];
    	else return tr[u].rh * p[tr[u].l - l + 1];
    }
    else
    {
    	pushdown(u);
    	int mid = tr[u].l + tr[u].r >> 1;
    	ull res = 0;
    	if (l <= mid) res += query(ls, l, r, st);
    	if (r > mid) res += query(rs, l, r, st);
    	pushup(u);
    	return res;
    }
}

void get_primes()
{
    for (int i = 2; i <= n; i++)
    {
    	if (!minp[i]) prime[cnt++] = i, minp[i] = i; 
    	for (int j = 0; prime[j] <= n / i; j++)
    	{
    	    minp[prime[j] * i] = prime[j];
    	    if (i % prime[j] == 0) break;
    	}
    }
}

int main()
{
    cin >> n >> m >> s;

    p[0] = f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
    	p[i] = p[i - 1] * P;
    	f[i] = f[i - 1] + p[i];
    }
	
    get_primes();
    build(1, 1, n);
	
    while (m--)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if (!op)
        {
            char c;
            cin >> c;
    	    modify(1, l, r, (ull)c);
    	}
    	else
    	{	
            int len = r - l + 1, res = r - l + 1;
            if (len == 1 || query(1, l + 1, r, op) == query(1, l, r - 1, op)) cout << 1 <<  endl;
            else
            {
                while (len > 1)
                {
                    int x = res / minp[len];
                    if (query(1, l + x, r, op) == query(1, l, r - x, op)) res /= minp[len];
                    len /= minp[len];
                }
                cout << res << endl;
            }
        }
    }
	
    return 0;
}

H. 聪明且狡猾的恶魔

博弈题，当只剩下 \(n-1\) 号和 \(n\) 号两个恶魔时，无论n号恶魔是否同意，\(n-1\) 号恶魔一定会获得所有金币，所以 \(n\) 号恶魔不会让 \(n-1\) 号恶魔当上老大，再往前推，剩下 \(3\) 个恶魔时，\(n\) 号恶魔一定支持 \(n-2\) 号恶魔，并且 \(n-2\) 号恶魔为了获得 \(n\) 号恶魔的支持，会支付1枚金币，因此，\(n-1号\) 恶魔不会让 \(n-2\) 号恶魔当上老大，层层递推，最终推出 \(1\) 号恶魔能获得的最大金币数

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

int T;
int n, x;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> x >> n;
        
        if (n % 2) cout << x - n / 2 << endl;
        else cout << x - n / 2 + 1 << endl;
    }
    
    return 0;
}

I. 马拉松

\(bfs\) 处理出 \(x\) 到 \(y\) 的马拉松路径，再用 \(dfs\) 计算出以 \(x\) 为根的子树除去路径后的节点数和以 \(y\) 为根的子树除去路径后的节点数，两数相乘即为答案

code:

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 300010;

int n, x, y;
vector<int> h[N];
int d[N];
int fx, fy;
int f[N];

void dfs(int u, int father)
{
    f[u]++;
    for (int i = 0; i < h[u].size(); i++)
    {
        int j = h[u][i];
        if (j == father) continue;
        dfs(j, u);
        f[u] += f[j];
    }
}

void bfs()
{
    queue<int> q;
    memset(d, -1, sizeof d);
    d[x] = 0;
    q.push(x);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < h[t].size(); i++)
        {
            int j = h[t][i];
            if (~d[j]) continue;
            d[j] = d[t] + 1;
            q.push(j);
        }
    }
    
    if (d[y] == 1) fx = y, fy = x;
    
    int u = y;
    for (int i = d[y] - 1; i >= 1; i--)
    {
        for (int j = 0; j < h[u].size(); j++)
            if (d[h[u][j]] == i)
            {
                u = h[u][j];
                if (i == d[y] - 1) fy = u;
                if (i == 1) fx = u;
                break;
            }
    }
}

signed main()
{
    cin >> n >> x >> y;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b), h[b].push_back(a);
    }
    
    bfs();
    
    dfs(x, fx);
    dfs(y, fy);
    
    cout << f[x] * f[y] << endl;
    
    return 0;
}

J. 尖塔第四强的高手

\(lca\) 板子题，每次查询中处理出点集的最近公共祖先，输出即可

code:

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1000010;

int n, r, q;
vector<int> h[N];
int f[N][20], dep[N];
int p[N], cnt;

void dfs(int u, int father)
{
    dep[u] = dep[father] + 1;
    f[u][0] = father;

    for (int i = 1; i <= 15; i++) 
        f[u][i] = f[f[u][i - 1]][i - 1];

    for (int i = 0; i < h[u].size(); i++)
        if (h[u][i] != father)
            dfs(h[u][i], u);
}

int lca(int u, int v)
{	
    if (dep[u] < dep[v]) swap(u, v);

	bool flag = false;
	if (u == 7 && v == 9) flag = true;
	
    for (int i = 15; i >= 0; i--)
        if (dep[f[u][i]] >= dep[v])
            u = f[u][i];
    
    if (flag) cout << u << ' ' << v << endl;    
            
    if (u == v) return u;

    for(int i = 15; i >= 0; i--)
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];

    return f[u][0];
}

void init()
{
    p[cnt++] = 1, p[cnt++] = 2;
    while (p[cnt - 1] < N)
    {
        p[cnt] = p[cnt - 1] + p[cnt - 2];
        cnt++;
    }
}

signed main()
{
    init();
    
    cin >> n >> r >> q;
    for (int i = 0; i < n - 1; i++)
    {
    	int a, b;
    	cin >> a >> b;
    	h[a].push_back(b);
    	h[b].push_back(a);
    }
    
    dfs(r, 0);
    
    while (q--)
    {
    	int x, k;
    	cin >> x >> k;
    	
    	int t = 0;
    	if (k <= cnt && x + p[k - 1] <= n) t = x + p[k - 1];
    	
    	int c = k;
    	while (c < cnt && x + p[c] <= n) t = lca(t, x + p[c++]);
    	
    	cout << t << endl;
    }
}

K. 比赛

树状数组模板题，分别计算每个点左右两边大于等于、小于等于、等于该点的数的个数，做一下容斥即可

code:

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200010;

int T;
int n;
int a[N], b[N], c[N];
int s1[N], s2[N];
int f1[N], f2[N];
int c1[N], c2[N];
int cnt1[N], cnt2[N];

int lowbit(int x)
{
    return x & -x;
}

void modify(int s[], int x, int k)
{
    while (x <= n)
    {
        s[x] += k;
        x += lowbit(x);
    }
}

int query(int s[], int x)
{
    int res = 0;
    while (x)
    {
        res += s[x];
        x -= lowbit(x);
    }
    return res;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        for (int i = 1; i <= n; i++) c[i] = a[i];
        sort(c + 1, c + 1 + n);
        
        for (int i = 1; i <= n; i++)
        {
            int l = 1, r = n;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (c[mid] < a[i]) l = mid + 1;
                else r = mid;
            }
            b[i] = l;
        }
    	
        for (int i = 1; i <= n; i++)
        {
            f1[i] = query(s1, b[i]);
            modify(s1, b[i], 1);
        }
        for (int i = n; i >= 1; i--)
        {
            f2[i] = query(s2, n - b[i] + 1);
            modify(s2, n - b[i] + 1, 1);
        }
        
        int res = 0;
        for (int i = 1; i <= n; i++) 
        {
            res += f1[i] * f2[i];
            s1[i] = s2[i] = f1[i] = f2[i] = 0;
        }
        
        for (int i = 1; i <= n; i++)
        {
            c1[i] = cnt1[b[i]]++;
            f1[i] = query(s1, n - b[i] + 1);
            modify(s1, n - b[i] + 1, 1);
        }
        for (int i = n; i >= 1; i--)
        {
            c2[i] = cnt2[b[i]]++;
            f2[i] = query(s2, b[i]);
            modify(s2, b[i], 1);
        }
        
        for (int i = 1; i <= n; i++) 
        {
            res += f1[i] * f2[i] - c1[i] * c2[i];
            s1[i] = s2[i] = f1[i] = f2[i] = c1[i] = c2[i] = cnt1[i] = cnt2[i] = 0;
        }
        
        cout << res << endl;
    }
    
    return 0;
}

L. 抓字符

概率 \(dp\)，计算出非严格单调上升子序列的概率和非严格单调子序列的概率以及只有一种元素子序列的概率，容斥求出答案

code:

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
#include <bits/stdc++.h>

#define int long long
#define endl '\n'

const int N = 1000010, mod = 998244353;

using namespace std;

int n;
int p[N];
string s;
int f1[2][30], f2[2][30], f3[2][30];
int h[N];

int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init()
{
	for (int i = 1; i < N; i++) h[i] = qmi(i, mod - 2);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	init();
	
    cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> p[i];
 	   
    s = ' ' + s;
    
    f1[0][0] = f2[0][0] = f3[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
    	for (int j = 0; j <= 26; j++)
        {
    		f1[i & 1][j] = f1[i - 1 & 1][j] * (p[i] - 1) % mod * h[p[i]] % mod;
            f2[i & 1][j] = f2[i - 1 & 1][j] * (p[i] - 1) % mod * h[p[i]] % mod;
            f3[i & 1][j] = f3[i - 1 & 1][j] * (p[i] - 1) % mod * h[p[i]] % mod;
        }
        for (int j = 0; j <= 26; j++)
        {
            if (j <= s[i] - 'a' + 1 || !j)
                f1[i & 1][s[i] - 'a' + 1] = (f1[i & 1][s[i] - 'a' + 1] + f1[i - 1 & 1][j] * h[p[i]] % mod) % mod;
            if (j >= s[i] - 'a' + 1 || !j)
                f2[i & 1][s[i] - 'a' + 1] = (f2[i & 1][s[i] - 'a' + 1] + f2[i - 1 & 1][j] * h[p[i]] % mod) % mod;
            if (j == s[i] - 'a' + 1 || !j)
                f3[i & 1][s[i] - 'a' + 1] = (f3[i & 1][s[i] - 'a' + 1] + f3[i - 1 & 1][j] * h[p[i]] % mod) % mod;
        }
    }
    
    int sum = 1;
    for (int i = 1; i <= n; i++) sum = sum * (p[i] - 1) % mod * h[p[i]] % mod;
    
    int res = 0;
    for (int i = 1; i <= 26; i++)
    {
    	res = (res + f1[n & 1][i]) % mod;
    	res = (res + f2[n & 1][i]) % mod;
    	res = (res - f3[n & 1][i] + mod) % mod;
    }
    
    cout << res << endl;
    
    return 0;
}