Count

题目大意

给定三个数，问所有元素都为1~m的整数且前k个元素与后k个元素分别对应相同的方案数。

解题思路

k为n时，前n个与后n个分别对应相同，那么就相当于没有限制条件，每个数可以有m种填法，直接即可

k不为n时，前k个元素与后k个元素对应相同，相当于固定了k个元素，自己能选择的有n-k个元素，即是答案。

时间复杂度：快速幂

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
const int mod=998244353;

//a ^ b mod p
int qpow(int a,int b,int p){
    long long res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=(long long)a*a%p;
        b>>=1;
    }
    return res;
}

bool multi=1;
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    if(k==n) cout<<qpow(m%mod,n,mod)<<endl;
    else cout<<qpow(m%mod,n-k,mod)<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Tree

题目大意

给你一棵树和每个结点的颜色，问你任意两点之间最短路径形成的三种颜色数量相同的路径数量。

解题思路

点分治。

考虑把一棵树以重心（其实是周围的最大子树数量小于等于n/2的结点，这样可以保证logn层，使时间复杂度控制在，不一定要重心），然后对于重心周围的若干个子树如tr1,tr2,tr3,tr4，讨论形成答案的几种情况：

①两个结点都在同个子树上，直接继续分治即可

②有一个结点在重心，那么每次算从重心出发的颜色数，三者相同时累加答案

③两个结点在不同的子树，我们可以开一个桶，先遍历tr1记录所有颜色相关信息，再遍历tr2的时候将信息对应桶中符合情况的进行累加，这时就能处理出tr1和tr2形成三种颜色相同的数量，再加入到桶中，接着遍历tr3，同样对应桶中累加，这时就能处理出tr3和前两棵树形成三种颜色相同的数量，再加入到桶中，直到把所有子树处理完。

然后往周围子树接着分治递归。

那么如果处理桶？

对于三种颜色的数量，我们只需要一个二元组pair，存储即可，first存的是b颜色数量减a颜色数量，second存c颜色数量减b颜色数量，一个二元组对应三种颜色数量，两个路径相加三种颜色数量相同时，即两个二元组相加得到{0,0},因此我们可以直接map[{-color[i].first,-color[i].second}]，的复杂度得到桶中能与当前路径相加得到三种颜色数量相同的数量。

时间复杂度：

(点分治，map容器)

参考代码

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

#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
//#define x first
//#define y second

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

const int mod=1e9+7;
const double eps=1e-8;
/*=================================*/
bool multi=0;
const int N=1e5+10,M=N<<1,INF=0x3f3f3f3f;
int n;
int h[N],e[M],ne[M],idx;
string s;
bool st[N];//表示这个点有没有被删去
PII q[N];
int ans;
int tms;

map<PII,int> mp;//桶

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int get_size(int u,int fa){
    if(st[u]) return 0;
    int res=1;
    for(int i=h[u];~i;i=ne[i]){
        if(e[i]!=fa){
            res+=get_size(e[i],u);
        }
    }
    return res;
}

int get_wc(int u,int fa,int tot,int &wc){
    if(st[u]) return 0;
    int sum=1,ms=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        int t=get_wc(j,u,tot,wc);
        ms=max(ms,t);
        sum+=t;
    }
    ms=max(ms,tot-sum);
    if(tms>ms){//我这里找的是重心，怕被卡常，其实不用找真正的重心也可以过，只需要ms<=tot/2就可以把重心wc赋值成u了
        tms=ms;
        wc=u;
    }
    return sum;
}

void get_dist(int u,int fa,PII dist,int &qt){
    if(st[u]) return;
    dist.first+=(s[u]=='b')-(s[u]=='a');
    dist.second+=(s[u]=='c')-(s[u]=='b');
    q[qt++]=dist;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        get_dist(j,u,dist,qt);
    }
}

void calc(int u){
    if(st[u]) return;
    tms=INF;
    get_wc(u,-1,get_size(u,-1),u);//找重心
    st[u]=true;//删去重心
    int pt=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i],qt=0;
        PII tmp={0,0};//重心的颜色信息
        tmp.first+=(s[u]=='b')-(s[u]=='a');
        tmp.second+=(s[u]=='c')-(s[u]=='b');
        get_dist(j,u,{0,0},qt);
        for(int k=0;k<qt;k++){
            auto &t=q[k];
            if(t.first+tmp.first==0&&t.second+tmp.second==0) ans++;//一个结点在重心的情况
            ans+=mp[{-t.first,-t.second}];//两个结点在不同子树的情况
        }  
        for(int k=0;k<qt;k++){
            auto &t=q[k];
            mp[{t.first+tmp.first,t.second+tmp.second}]++;
        }
    }
    mp.clear();
    for(int i=h[u];~i;i=ne[i]) calc(e[i]);//向周围子树递归
}

void solve(){
    cin>>n;
    cin>>s;
    s=' '+s;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    calc(1);
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Calculate

题目大意

给定一个有n个顶点的有向图，每个顶点有两个权值，每个顶点有且只有一条出边。

接下里有q个询问，每次询问从起点出发走步后的结果，起初权值是y，每走一步会变成y’=y*ki+bi

解题思路

倍增法，定义为从点走步能到的点，、分别表示从点走步的系数和常数。

正因为系数和常数满足结合律，所以可以这么做，起初权值为y，走一步变成，走两步变成，相当于系数从，常数项从，可以发现，系数每次乘上k，常数先乘k再加b。

首先我们根据读入获得j=0的情况，也就是i点跳到下一个点的信息，然后根据递推式子算出所有情况。

处理询问时，根据二进制的性质，可以把走l步分解成若各干二进制数相加来达到每次询问

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod = 1e9 + 7;
bool multi=1;

const int N = 1e5 + 10;
int k[N], b[N], to[N][35];
struct Node{
    int k, b;
}a[N][35];
int n, q;

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> k[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> to[i][0];
    for(int i = 1; i <= n; i++){
        a[i][0].k=k[to[i][0]];
        a[i][0].b=b[to[i][0]];
    }
    for(int i = 1; i <= 30; i++){
        for(int j = 1; j <= n; j++){
            a[j][i].k = a[j][i - 1].k * a[to[j][i - 1]][i - 1].k % mod;
            a[j][i].b = (a[j][i - 1].b * a[to[j][i - 1]][i - 1].k + a[to[j][i - 1]][i-1].b) % mod;
            to[j][i] = to[to[j][i - 1]][i - 1];
        }
    }
    while(q--){
        int x, l, y, kk = 1, bb = 0;
        cin >> x >> l >> y;
        for(int i = 30; i >= 0; i--){
            if(l - (1LL << i) >= 0){
                l -= 1LL << i;
                kk = kk * a[x][i].k % mod;
                bb = (bb * a[x][i].k + a[x][i].b) % mod;
                x = to[x][i];
            }
        }
        cout << (y * kk + bb) % mod<< '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Perfect square number

题目大意

给定一个序列，你可以选择一个数，将该数变成1~300中的任意一个数，问连续子段和是平方数的最大数量。

解题思路

这题的数据范围是300，意味着我们可以用去预处理或计算结果。

我们可以先求原数组的子段和是平方数的数量，然后再减去与pos位置相关的构成子段和是平方数的数量，加上将pos位置数修改后与pos位置相关的构成子段和是平方数的数量。

对于每个pos的修改，我们可以先预处理所有跨过pos但是去掉a[pos]的所有子段和放在桶中，然后对pos的原数组通过桶中每个平方数减去pos位置原来的数得到旧值，再通过桶中每个平方数减去pos位置要修改成的数得到新值。答案就是原数组子段和为平方数的数量减去旧值加上新值这样的最大值。

参考代码

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>
using namespace std;
#define int long long
#define endl '\n'

bool multi=1;

const int N = 310;
int n;
int a[N],s[N];
bool st[N*N];
int mp[N * N];
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    int cnt = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            if(st[s[j] - s[i - 1]]) cnt++;
        }
    }
    for(int pos = 1; pos <= n; pos++){
        memset(mp, 0, sizeof mp);
        for(int i = 1; i <= pos; i++){
            for(int j = pos; j <= n; j++){
                mp[s[j] - s[i - 1] - a[pos]]++;
            }
        }
        for(int i = 1; i <= 300; i++){
            int oldv = 0, newv = 0;
            for(int j = 1; j <= 300; j++){
                if(j * j >= a[pos])
                    oldv += mp[j * j - a[pos]];
                if(j * j >= i)
                    newv += mp[j * j - i];
            }
            ans = max(ans, cnt + newv - oldv);
        }
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;

    for(int i = 1; i * i < N * N; i++){
        st[i * i] = true;
    }

    while(T--){
        solve();
    }

    return 0;
}