算法竞赛

SDOI 2018二试题解

Posted by attack204 on 2019-05-04

虽然一轮之后就退役了但是二轮还是要去划划水呀~

然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉，烤前感觉也没啥可复习的，就补一补去年二轮的题吧。

题目思路基本都参考自shadowice神仙Orz

Day2T1没时间做了咕咕咕

物理实验

充满毒瘤气息的计算几何题。。

首先旋转一下坐标系，那么只需要考虑两条线平行于$y$轴的情况。

由于题目中规定每个挡板都不和直线导轨接触，因此一定是分别分布于$y > 0$和$y < 0$两部分，我们分别维护。

现在只考虑上半部分，不难看出对于两条线段一上一下的情况，上面的线段被遮挡的部分是没有用的。同时所有的线段我们可以拆成加入和删除两个事件，首先预处理出两个事件之间的最大的sec，同时有了距离就可以算出答案。

然后双指针扫一下。

复杂度$O(n \log n)$

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
#include<bits/stdc++.h> 
#define fi first
#define se second
#define LL long long
#define pb push_back
#define double long double   
using namespace std;
const int MAXN = 1e6 + 10;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
};
int N, opt[MAXN];
double x[MAXN][2], y[MAXN][2], pos[MAXN], bx, by, ex, ey, L;
double nx, val[MAXN], sec[MAXN];
struct Segment {
    int id;
    bool operator < (const Segment &rhs) const {
        if(id == rhs.id) return 0;
        int td = rhs.id;
        double va = (y[id][1] - y[id][0]) / (x[id][1] - x[id][0]) * (nx - x[id][0]) + y[id][0];
        double vb = (y[td][1] - y[td][0]) / (x[td][1] - x[td][0]) * (nx - x[td][0]) + y[td][0];
        return abs(va) < abs(vb);
    }
};
set<Segment> su, sd;
double GouGu(double x, double y) {
    return sqrt(x * x + y * y);
}
int comp(int a, int b) {
    return (a < 0 ? x[-a][1] : x[a][0]) < (b < 0 ? x[-b][1] : x[b][0]);
}
void init() {
    nx = 0; memset(val, 0, sizeof(val));
}
void solve() {
    N = read();
    init();
    for(int i = 1; i <= N; i++) {
        x[i][0] = read(); y[i][0] = read(); x[i][1] = read(); y[i][1] = read();
    }
    bx = read(), by = read(); ex = read(); ey = read(); L = read();
    double dx = ex - bx, dy = ey - by, dis = GouGu(dx, dy);
    double bl = (bx == by) ? 0 : by - dy / dx * bx;
    for(int i = 1; i <= N; i++) y[i][0] -= bl, y[i][1] -= bl;
    dx /= dis; dy /= dis;//dx cos dy sin
    //(x, y) 
    for(int i = 1; i <= N; i++) {
        double px1 = x[i][0], px2 = x[i][1], py1 = y[i][0], py2 = y[i][1];
        x[i][0] = dx * px1 + dy * py1; //tag
        y[i][0] = dx * py1 - dy * px1;
        x[i][1] = dx * px2 + dy * py2;
        y[i][1] = dx * py2 - dy * px2;
        if(x[i][0] > x[i][1]) swap(x[i][0], x[i][1]), swap(y[i][0], y[i][1]);
        sec[i] = GouGu(x[i][1] - x[i][0], y[i][1] - y[i][0]) / (x[i][1] - x[i][0]);
    }
    for(int i = 1; i <= 2 * N; i++) opt[i] = (i <= N ? -i : i - N);
    sort(opt + 1, opt + 2 * N + 1, comp);
    for(int i = 1; i <= 2 * N; i++) {
        int u;
        if(opt[i] > 0) {//insert
            u = opt[i];
            nx = pos[i] = x[u][0];
            (y[u][0] > 0 ? su : sd).insert({u});
        } else {//delet
            u = -opt[i];
            nx = pos[i] = x[u][1];
            (y[u][0] > 0 ? su : sd).erase({u});
        }	
        if(!su.empty()) val[i] += sec[su.begin()->id];
        if(!sd.empty()) val[i] += sec[sd.begin()->id];
    }
    for(int i = 2 * N; i >= 1; i--) val[i] = val[i- 1];
    double ret = 0, rl = pos[1] - L, rr = pos[1], ans = 0;
    int pl = 1, pr = 2;
    while(pr <= 2 * N) {
        double dl = pos[pl] - rl, dr = pos[pr] - rr;
        if(dl > dr)      ret += (val[pr] - val[pl]) * dr, pr++, rl += dr, rr += dr;
        else if(dr > dl) ret += (val[pr] - val[pl]) * dl, pl++, rl += dl, rr += dl;
        else ret += (val[pr] - val[pl]) * dl, pr++, pl++, rl += dl, rr += dl;
        ans = max(ans, ret);
    }
    printf("%.15Lf\n", ans);
}
signed main() {
    for(int T = read(); T--; solve());
    return 0;
}

战略游戏

首先建出圆方树，那么答案为包含所有询问点的最小联通块大小 减去关键点个数

最小联通块大小可以转化为边的贡献最后特判LCA，将所有点按dfs序排序后算出相邻两点的dis，最后/2即可

复杂度$O(n log n)$

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
#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long
#define pb push_back  
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7;
const LL INF = 1e18 + 10;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, nd;
vector<int> v[MAXN], E[MAXN];
int dfn[MAXN], low[MAXN], times, st[MAXN], tp;
void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++times;
    st[++tp] = x;
    for(auto &to : v[x]) {
        if(to == fa) continue;
        if(!dfn[to]) {
            tarjan(to, x), chmin(low[x], low[to]);
            if(low[to] >= dfn[x]) {
                E[++nd].pb(x); E[x].pb(nd);
                do {
                    E[nd].pb(st[tp]); E[st[tp]].pb(nd);
                }while(st[tp--] != to);
            }
        }
        else chmin(low[x], dfn[to]);

    }
}
int dis[MAXN], siz[MAXN], son[MAXN], top[MAXN], dep[MAXN], ffa[MAXN];
void dfs(int x, int fa) {
    siz[x] = 1; ffa[x] = fa;
    for(auto &to : E[x]) {
        if(to == fa) continue;
        dis[to] = dis[x] + (to <= N);
        dep[to] = dep[x] + 1;
        dfs(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf; dfn[x] = ++times;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(auto &to : E[x]) {
        if(top[to]) continue;
        dfs2(to, to);
    }
}
int LCA(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = ffa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
int Dis(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[LCA(x, y)];
}
int comp(int a, int b) {
    return dfn[a] < dfn[b];
}
void init() {
    for(int i = 1; i <= N; i++) v[i].clear();
    for(int i = 1; i <= nd; i++) E[i].clear();
#define m0(x) memset(x, 0, sizeof(x))
    m0(top); m0(dfn); m0(low); m0(dis); m0(dep); m0(son); m0(ffa); m0(siz); m0(dis);
#undef m0
    tp = 0; times = 0; nd = 0;
    
}
int ggg = 0;
void solve() {
    N = read(); M = read();
    init();
    nd = N;
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read();
        v[x].pb(y); v[y].pb(x);		
    }
    tarjan(1, 0);
    dfs(1, 0);
    dfs2(1, 1);
    int Q = read();
    for(int k = 1; k <= Q; k++) {
        int num = read(); LL ans = 0;
        vector<int> po;
        for(int i = 1; i <= num; i++) po.pb(read());
        sort(po.begin(), po.end(), comp);
        for(int i = 0; i < po.size() - 1; i++) {
            ans += Dis(po[i], po[i + 1]);
        }
        ans += Dis(po[num - 1], po[0]);
        ans = ans  / 2 + (LCA(po[0], po[num - 1]) <= N) - num;
    cout << ans << '\n';

    }
}

signed main() {
    for(int T = read(); T--; solve());
    return 0;
}

反回文串

神仙反演Orzzzzzzzzzz

首先一个串的本质不同的轮换个数是不重叠最小循环节的长度

如果最小循环节的长度$d$是偶数，此时一个回文串的$d$种不同的轮换字符串当中恰好有两个回文串(本身一个，把前$\frac{d}{2}$个字符拼到后面一个)

否则$d$是奇数的话一定会有$d$个本质不同的字符串

首先考虑字符集为$k$的情况下回文串的数量$g(n)$

显然$g(n) = k^{\lfloor\frac{n+1}{2} \rfloor}$(固定一半)

那么设

设$f(i)$表示最小循环节为$i$的字符串数量，显然有

$Ans(n) = \sum_{d|n} h(d) f(d)$

$f(d)$很难直接求，但是我们可以枚举循环节得到一个等式

反演一下

带入原来的公式

我们尝试枚举$g$

把$d$拆为$d = d’ * K$，我们去枚举新的$d’$

之前我们发现$h$函数有比较好的性质，这里似乎可以直接把$d$提出来。分析一下不难发现，只有当$d$是偶数且$k$是奇数是不能直接提。因为一个奇数不会有偶数因子，那么$\frac{n}{k}$一定是偶数

此时把式子中的$k$提出来，考虑一下$k\sum_{d|\frac{n}{k}} h(d)\mu(d)$的值，打一下表可以发现值总是$0$，因为$2$这个因子使得$mu$为$\pm 1$的项消掉了

那么在计算这时候直接把这种情况判掉就可以

原式变为

然后直接对$n$进行Pollard-Rho分解，分解的同时可以求出后面的值，拿个map存一下。

然后dfs枚举约数直接算就行了

复杂度玄学，但是出题人把$n$出到$10^{18}$也只能这么干。。

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
#include<bits/stdc++.h> 
#define fi first
#define se second
#define int long long 
#define LL long long
#define pb push_back  
using namespace std;
const int MAXN = 1e6 + 10;
const LL INF = 1e18 + 10;
int mod;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
LL mul(LL a, LL b, int mod = mod) {
    //a %= mod, b %= mod;
    return ((a * b - (LL)((LL)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod;
}
int fp(int a, int p, int mod = mod) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a, mod);
        a = mul(a, a, mod); p >>= 1;
    }
    return base;
}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, K;
int st, ans;
vector<int> ds;
unordered_map<LL, LL> t, vds;
const int Tn = 9;
int Cbase[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
bool CheckP(int p) {
    if(p == 1) return 0;
    for(int i = 0; i < Tn; i++) if(p == Cbase[i]) return 1;
    for(int id = 0; id < Tn; id++) {
        int v = Cbase[id];
        int lim = 0, t = p - 1, pre = 1;
        while(t && (!(t & 1))) lim++, t>>= 1; t = fp(v, t, p);
        while(lim--) {
            t = mul(t, t, p);
            if(t == 1 && (pre != p - 1 && pre != 1)) return 0;
            pre = t;
        }
        if(t != 1) return 0;
    }
    return 1;
}

int rnd() {
    return rand();
}
int gcd(int a, int b) {
    return (!b) ? a : gcd(b, a % b);
}
int rd(int base, int mod) {
    return (mul(base, base, mod) + st) % mod;
}
int myabs(int x, int y) {
    return (x > y) ? x - y : y - x;
}

void Rho(int x) {
    if(x == 1) return ;
    if(CheckP(x)) {
        vds[x]++;
        return ;
    }
    while(1) {
        st = rand() % x + 1;
        int v1 = rnd() % x + 1, g = gcd(x, v1);
        if(g != 1 && g != x) {Rho(g); Rho(x / g); return ;}
        int v2 = v1; v1 = rd(v1, x);
        for(int k = 0, tr = 1; v1 - v2; v1 = rd(v1, x), k++) {
            g = gcd(x, myabs(v1, v2));
            if(g != 1 && g != x) {Rho(g); Rho(x / g); return ;}
            if(k == tr) {v2 = v1; tr <<= 1;}
        }
    }
}
void Clear() {
    ds.clear();	
    vds.clear();
    ans = 0;
}
int g(int x) {
    return fp(K, (x + 1) / 2);
}
int h(int x) {
    return (x & 1) ? x : x / 2;
}

void dfs(int n, int num, int cur, unordered_map<LL, LL>::iterator now) {
    if(now == vds.end()) {
        ds.pb(num);
        t[num] = cur;
        return ;
    }
    int nn = now->se, vv = now->fi, vvd = (1 - now->fi), nv = vv, nvd = vvd; auto nxt = ++now;
    dfs(n + 1, num, cur, nxt);
    for(int i = 1; i <= nn; i++) {
        dfs(n + 1, num * nv, cur * vvd, nxt);
        nv *= vv; nvd *= vvd;
    }
}
void print(int x) {
    if(x > 9) print(x / 10);
    putchar('0' + x % 10);
}
void solve() {
    Clear();
    N = read(); K = read(); mod = read(); K %= mod;
    Rho(N);
    dfs(0, 1, 1, vds.begin());
    for(auto &num: ds) {
        if((num & 1) && (!((N / num) & 1))) continue;
        add2(ans, mul(g(num), mul(h(num), t[N / num])));	
    }
    print(ans); putchar('\n');
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
#endif
    srand(20020113);
    for(int T = read(); T--; solve());
    return 0;
}

旧式题

我实在不想照着题解抄一遍公式了qwq

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
141
142
143
144
145
146
147
#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
#define LL long long 

const int MAXN = 2e5 + 10, mod = 1e9 + 7;
using namespace std;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
inline int read() {
	char c = getchar(); int x = 0, f = 1;
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}
int mu[MAXN], prime[MAXN], vis[MAXN], tot, A, B, C, num, deg[MAXN];
int fa[MAXN], fb[MAXN], fc[MAXN];
vector<LL> di[MAXN];
vector<Pair> v[MAXN];//每个数的质因数分解 
struct Edge {
	LL u, v, w;
}E[MAXN * 10];
void GetPrime(int N) {
	vis[1] = 1; mu[1] = 1;
	for(int i = 2; i <= N; i++) {
		if(!vis[i]) prime[++tot] = i, mu[i] = -1;
		for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
			vis[i * prime[j]] = 1;
			if(i % prime[j]) mu[i * prime[j]] = -mu[i];
			else {mu[i * prime[j]] = 0; break;}
		}
	}
	for(int i = 1; i <= tot; i++) 
		for(int j = 1; j * prime[i] <= N; j++) 
			di[j * prime[i]].push_back(prime[i]);
		
}

void Get(int *a, int N, int X) {
	for(int i = 1; i <= N; i++)
		for(int j = i; j <= N; j += i) a[i] += X / j;
}
LL lcm(int a, int b) {
	return 1ll * a / __gcd(a, b) * b;
}
void init() {
	memset(fa, 0, sizeof(fa));
	memset(fb, 0, sizeof(fb));
	memset(fc, 0, sizeof(fc));
	memset(deg, 0, sizeof(deg));
	num = 0;
	for(int i = 1; i <= A; i++) v[i].clear();
}
void Build() {
	for(int w = 1; w <= A; w++) {//lcm(u, v) = w;
		if(!mu[w]) continue;
		int n = di[w].size();
		//for(auto x : di[w]) printf("%d ", x); puts("");
		for(int sta = 0; sta < (1 << n); sta++) {
			LL i = 1;
			for(int b = 0; b < n; b++) 
				if(sta >> b & 1) i *= di[w][b];
			for(int s = sta; ; s = sta & (s - 1)) {//tag
				LL g = 1;
				for(int b = 0; b < n; b++) 
					if(s >> b & 1) 
						g *= di[w][b];
				int j = w * g / i; 
				if(i < j) E[++num] = {i, j, w};// printf("%d\n", num);
				if(!s) break;
			}
		}
	}
}

LL fuck(int x, int y, int w) {
	if(mu[x] == 1) 
		return add(add(mul(mul(fa[w], fb[w]), fc[y]), mul(mul(fa[w], fb[y]), fc[w])), mul(mul(fa[y], fb[w]), fc[w]));
	else 
		return (-add(add(mul(mul(fa[w], fb[w]), fc[y]), mul(mul(fa[w], fb[y]), fc[w])), mul(mul(fa[y], fb[w]), fc[w])) + mod) % mod;
}

LL calc() {
//	for(int i = 1; i <= A; i++) for(auto &x : v[i])printf("%d %d %d\n", i, x.fi, x.se);
	for(int i = 1; i <= num; i++) {
		int x = E[i].u, y = E[i].v;
		if(deg[x] > deg[y]) swap(x, y);
		v[y].push_back(MP(x, E[i].w));
	}
	LL ans = 0;
	for(int a = 1; a <= A; a++) {
		for(auto &t1 : v[a]) {
			LL b = t1.fi, w1 = t1.se;
			for(auto &t2 : v[b]) {
				LL c = t2.fi, w2 = t2.se, xi = mu[a] * mu[b] * mu[c];
				LL w3 = lcm(a, c);
				if(w3 > A) continue;
				if(xi == 1) {
					add2(ans, mul(mul(fa[w1], fb[w2]), fc[w3]));
					add2(ans, mul(mul(fa[w1], fb[w3]), fc[w2]));
					add2(ans, mul(mul(fa[w2], fb[w1]), fc[w3]));
					add2(ans, mul(mul(fa[w2], fb[w3]), fc[w1]));
					add2(ans, mul(mul(fa[w3], fb[w1]), fc[w2]));
					add2(ans, mul(mul(fa[w3], fb[w2]), fc[w1]));
				} else if(xi == -1) {
					add2(ans, mul(mul(-fa[w1], fb[w2]), fc[w3]));
					add2(ans, mul(mul(-fa[w1], fb[w3]), fc[w2]));
					add2(ans, mul(mul(-fa[w2], fb[w1]), fc[w3]));
					add2(ans, mul(mul(-fa[w2], fb[w3]), fc[w1]));
					add2(ans, mul(mul(-fa[w3], fb[w1]), fc[w2]));
					add2(ans, mul(mul(-fa[w3], fb[w2]), fc[w1]));					
				}
			//	cout << ans << endl;
			}
		}
	}

	for(int i = 1; i <= num; i++) {//有两个一样 
		add2(ans, fuck(E[i].u, E[i].v, E[i].w));
		add2(ans, fuck(E[i].v, E[i].u, E[i].w));
	}
	for(int i = 1; i <= C; i++) {//全都一样 
		if(mu[i] == 1) add2(ans, mul(mul(fa[i], fb[i]), fc[i]));
		else if(mu[i] == -1) add2(ans, -mul(mul(fa[i], fb[i]), fc[i]) + mod);
	}
		
	return ans;
}
void solve() {
	init();
	A = read(); B = read(); C = read();
	if(A < B) swap(A, B); if(C > B) swap(B, C); if(A < B) swap(A, B); 
	Get(fa, A, A); Get(fb, A, B); Get(fc, A, C);	
	Build();
	cout << calc() << '\n';
}
signed main() {
	GetPrime(2e5);
	for(int T = read(); T; T--, solve());
	return 0;
}

荣誉称号

每个位置$x$向$\frac{x}{2}$连边最终会得到一棵完全二叉树

题目转化为：给出一个有点权的树，对于每个点可以花费$b_i$的代价使点权增加$1$，问使得所有长度为$k + 1$的链的点权和$\% M$均为$0$的最小花费

首先考虑序列的情况，稍加归纳后不难得到$ai \equiv a{i + K + 1} \pmod M$

放到树上话那么最终一个点的权值一定和它的$K+1$级祖先相同，因此对于前$2^{k}$个点，我们$O(nm)$预处理出$w[x][y]$表示$x$的点为$y$时，所有能被它限制的点的代价

现在只需要考虑前$2^{k+1}-1$个点，首先把标号$< 2^k$的叶子节点删掉，对于剩下的点的限制条件变为所有叶子节点到根的路径和$\% M =0$。那么设$f[i][j]$表示以$i$为根的子树，到所有叶子节点的权值$\%M = j$的最小代价，转移的时候暴力枚举该点的取值。

复杂度$O(nm + 2^k m^2)$可以拿到70分

考虑$w$的预处理，std在这里用了一个等差数列，实际上不用这么麻烦，因为$a[i]$取值只有$200$，直接对值域暴力就行

复杂度$O(n + 2^k m^2)$

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
#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long
#define pb push_back  
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e7 + 10, mod = 1e9 + 7;
const LL INF = 1e18 + 10;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int ch(int x, int l, int r) {
    return x >= l && x <= r;
}
int N, K, M, P, a[MAXN], mx[MAXN], n, jump, fa[MAXN], b[MAXN];
vector<int> bel[MAXN];
unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    N = read(); K = read(); M = read(); P = read(); SA = read(); SB = read(); SC = read(); A = read(); B = read();
    for(int i = 1; i <= P; i++) a[i] = read() % M, b[i] = read();
    for(int i = P + 1; i <= N; i++){
        a[i] = rng61() % A + 1;
        a[i] %= M;
        b[i] = rng61() % B + 1;
    }
}

LL w[(1 << 12) - 1][201];//w[i][j] 当i为j时，所有受i限制的点的代价 
LL f[(1 << 12) - 1][201], num[211];

void dfs(int x, int dep) {
    mx[x] = dep;
    if(dep > K + 1) bel[fa[x]].pb(x);
    int base = 2 * x;
    for(int i = 0; i <= 1; i++) {
        int to = 2 * x + i; if(to > N) continue;
        dfs(to, dep + 1);
        chmax(mx[x], mx[to]);
    }
}
LL get(int val, LL target, LL inc) {//在%M意义下把val变为target的最小花费 
    if(target >= val) return 1l * (target - val) * inc;
    return 1ll * ((M - val) + target) * inc;
}
void dfs2(int x) {
    if(x > n || mx[x] <= K) return ;
    if(x >= (1 << K)) {//叶节点 
        for(int i = 0; i < M; i++) f[x][i] = w[x][i];
        return ;
    }
    for(int i = 0; i < 2; i++) if(2 * x + i <= n) dfs2(2 * x + i);
    for(int i = 0; i < M; i++) {//与叶子节点的路径和%M = j 
        f[x][i] = INF;
        for(int j = 0; j < M; j++) {//该节点的增量
            LL sv = 0;
            for(int gg = 0; gg < 2; gg++) {
                int to = 2 * x + gg;
                if(to <= n) 
                sv += f[to][(i - a[x] - j + 2 * M) % M];
            }
            chmin(f[x][i], sv + w[x][(a[x] + j) % M]);
        }
    }
}

void solve() {
    gen();
    memset(f, 0, sizeof(f));
    memset(w, 0, sizeof(w));
    jump = 1; n = (1 << (K + 1)) - 1;
    for(int i = 1; i <= K + 1; i++) jump *= 2;
    for(int i = 1; i <= N; i++) {
     bel[i].clear();
    }

    for(int i = 1; i <= N; i++) fa[i] = (i <= n ? i : fa[i / jump]);
    dfs(1, 1);

    for(int i = 1; i < (1 << (K + 1)); i++) {
        memset(num, 0, sizeof(num));
        for(auto &son: bel[i]) num[a[son]] += b[son];
        for(int j = 0; j < M; j++) {
            w[i][j] += get(a[i], j, b[i]);
            for(int k = 0; k < M; k++) w[i][j] += get(k, j, num[k]);
        }
    }
    dfs2(1);
    cout << f[1][0] << '\n';
}
signed main() {
#ifndef ONLINE_JUDGE
    freopen("title-task3.in", "r", stdin);
#endif
    for(int T = read(); T--; solve());
    return 0;
}
FEATURED TAGS
算法竞赛
FRIENDS