杂题小记(2023.03.08)更好的阅读体验戳此进入LG-P8348 「Wdoi-6」未知之花魅知之旅LG-P3121 [USACO15FEB]Censoring GLG-P3172 [CQOI2015]选数LG-P3327 [SDOI2015]约数个数和LG-P1829 [国家集训队]Crash的数字表格 / JZPTABCF235E Number ChallengeLG-P4619 [SDOI2018]旧试题LG-P3704 [SDOI2017]数字表格UPD
考虑到限制可以转化为两个数相减或相加可以推出下一个数,然后发现相加操作可以被相减操作代替,同时发现多次相减可以合成,最后判一下减到最小的结果是否相同即可。
xxxxxxxxxx
711
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23template < typename T = int >
24inline T read(void);
25
26int main(){
27 int T = read();
28 while(T--){
29 int a = read(), b = read(), x = read(), y = read(), k = read();
30 auto Cal = [k](int &a, int &b)->void{
31 while(true){
32 if(a > b){
33 int cnt = (a - k) / b;
34 if(!cnt)return;
35 if(cnt & 1)a -= cnt * b, swap(a, b);
36 else a -= cnt * b;
37 }else if(a < b){
38 int cnt = (b - k) / a;
39 if(!cnt)return;
40 if(cnt & 1)b -= cnt * a, swap(a, b);
41 else b -= cnt * a;
42 }else return;
43 }
44 };
45 auto Check = [&](void)->bool{
46 if(a < k || b < k || x < k || y < k)return false;
47 if(a == x && b == y)return true;
48 Cal(a, b), Cal(x, y);
49 return a == x && b == y;
50 };
51 printf("%s\n", Check() ? "yes" : "no");
52 }
53 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54 return 0;
55}
56
57template < typename T >
58inline T read(void){
59 T ret(0);
60 int flag(1);
61 char c = getchar();
62 while(c != '-' && !isdigit(c))c = getchar();
63 if(c == '-')flag = -1, c = getchar();
64 while(isdigit(c)){
65 ret *= 10;
66 ret += int(c - '0');
67 c = getchar();
68 }
69 ret *= flag;
70 return ret;
71}
经典 AC 自动机,维护两个栈记录路径上的指针和答案即可,匹配到时弹出对应数量,并更新 AC 自动机上的指针。
xxxxxxxxxx
991
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29struct Node{
30 Node* tr[26];
31 Node* fail;
32 int len;
33 OPNEW;
34}nd[110000];
35ROPNEW_NODE;
36Node* root;
37
38basic_string < char > ans;
39
40void Insert(string S){
41 Node* p = root;
42 for(auto c : S){
43 if(!p->tr[d(c)])p->tr[d(c)] = new Node();
44 p = p->tr[d(c)];
45 }p->len = S.length();
46}
47void Build(void){
48 queue < Node* > cur;
49 cur.push(root);
50 while(!cur.empty()){
51 auto p = cur.front(); cur.pop();
52 for(int i = 0; i < 26; ++i)
53 if(p->tr[i])p->tr[i]->fail = p == root ? root : p->fail->tr[i], cur.push(p->tr[i]);
54 else p->tr[i] = p == root ? root : p->fail->tr[i];
55 }
56}
57void Accept(string S){
58 basic_string < Node* > cur;
59 cur += root;
60 Node* p = root;
61 for(auto c : S){
62 p = p->tr[d(c)];
63 ans += c, cur += p;
64 if(p->len){
65 for(int i = 1; i <= p->len; ++i)ans.pop_back(), cur.pop_back();
66 p = cur.back();
67 }
68 }
69}
70
71string pat, txt;
72
73int main(){
74 root = new Node();
75 cin >> txt;
76 int N = read();
77 while(N--)cin >> pat, Insert(pat);
78 Build(), Accept(txt);
79 for(auto c : ans)printf("%c", c);
80 printf("\n");
81 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
82 return 0;
83}
84
85template < typename T >
86inline T read(void){
87 T ret(0);
88 int flag(1);
89 char c = getchar();
90 while(c != '-' && !isdigit(c))c = getchar();
91 if(c == '-')flag = -1, c = getchar();
92 while(isdigit(c)){
93 ret *= 10;
94 ret += int(c - '0');
95 c = getchar();
96 }
97 ret *= flag;
98 return ret;
99}
考虑容斥,令
xxxxxxxxxx
711
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N, K, L, H;
29ll dp[110000];
30
31ll qpow(ll a, ll b){
32 ll ret(1), mul(a);
33 while(b){
34 if(b & 1)ret = ret * mul % MOD;
35 b >>= 1;
36 mul = mul * mul % MOD;
37 }return ret;
38}
39
40int main(){
41 N = read(), K = read(), L = read(), H = read();
42 L = (int)ceil((double)L / K), H = H / K;
43 auto F = [=](int val)->ll{
44 int l = (int)ceil((double)L / val), r = H / val;
45 if(l > r)return 0;
46 return ((qpow(r - l + 1, N) - (r - l + 1)) % MOD + MOD) % MOD;
47 };
48 for(int i = H - L; i >= 1; --i){
49 dp[i] = F(i);
50 for(int j = i + i; j <= H - L; j += i)
51 dp[i] = (dp[i] - dp[j] + MOD) % MOD;
52 }printf("%lld\n", dp[1] + (L == 1));
53 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54 return 0;
55}
56
57template < typename T >
58inline T read(void){
59 T ret(0);
60 int flag(1);
61 char c = getchar();
62 while(c != '-' && !isdigit(c))c = getchar();
63 if(c == '-')flag = -1, c = getchar();
64 while(isdigit(c)){
65 ret *= 10;
66 ret += int(c - '0');
67 c = getchar();
68 }
69 ret *= flag;
70 return ret;
71}
主要用到了公式:
后面的部分就是标准的莫反后数论分块了。
xxxxxxxxxx
831
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28ll F[LIM + 100];
29ll mu[LIM + 100], smu[LIM + 100];
30bitset < LIM + 100 > notPrime;
31basic_string < int > Prime;
32
33int main(){mu[1] = 1;
34 for(int i = 2; i <= LIM; ++i){
35 if(!notPrime[i])Prime += i, mu[i] = -1;
36 for(auto p : Prime){
37 if((ll)i * p > LIM)break;
38 mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
39 notPrime[i * p] = true;
40 if(i % p == 0)break;
41 }
42 }
43 for(int i = 1; i <= LIM; ++i)smu[i] = smu[i - 1] + mu[i];
44 for(int i = 1; i <= LIM; ++i){
45 int l = 1;
46 while(l <= i){
47 int r = i / (i / l);
48 F[i] += i / l * (r - l + 1);
49 l = r + 1;
50 }
51 }
52 int T = read();
53 while(T--){
54 ll ans(0);
55 int N = read(), M = read();
56 int lim = min(N, M);
57 int l = 1;
58 while(l <= lim){
59 int r = min(N / (N / l), M / (M / l));
60 ans += (smu[r] - smu[l - 1]) * F[N / l] * F[M / l];
61 l = r + 1;
62 }printf("%lld\n", ans);
63 }
64
65 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66 return 0;
67}
68
69template < typename T >
70inline T read(void){
71 T ret(0);
72 int flag(1);
73 char c = getchar();
74 while(c != '-' && !isdigit(c))c = getchar();
75 if(c == '-')flag = -1, c = getchar();
76 while(isdigit(c)){
77 ret *= 10;
78 ret += int(c - '0');
79 c = getchar();
80 }
81 ret *= flag;
82 return ret;
83}
标准莫反,没什么特别的,注意细节即可。
xxxxxxxxxx
921
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29int N, M;
30// ll F[LIM + 100];
31ll mu[LIM + 100], smu[LIM + 100];
32bitset < LIM + 100 > notPrime;
33basic_string < int > Prime;
34
35ll qpow(ll a, ll b){
36 ll ret(1), mul(a);
37 while(b){
38 if(b & 1)ret = ret * mul % MOD;
39 b >>= 1;
40 mul = mul * mul % MOD;
41 }return ret;
42}
43
44int main(){mu[1] = 1;
45 for(int i = 2; i <= LIM; ++i){
46 if(!notPrime[i])Prime += i, mu[i] = -1;
47 for(auto p : Prime){
48 if((ll)i * p > LIM)break;
49 mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
50 notPrime[i * p] = true;
51 if(i % p == 0)break;
52 }
53 }
54 for(int i = 1; i <= LIM; ++i)smu[i] = ((smu[i - 1] + mu[i] * i % MOD * i % MOD) % MOD + MOD) % MOD;
55 ll inv2 = qpow(2, MOD - 2);
56 auto CalF = [inv2](ll n, ll m)->ll{
57 return (n * (n + 1) / 2) % MOD * ((m * (m + 1) / 2) % MOD) % MOD;
58 };
59 ll ans(0);
60 N = read(), M = read();
61 int lim = min(N, M);
62 int l = 1;
63 while(l <= lim){
64 int r = min(N / (N / l), M / (M / l));
65 int cn = N / l, cm = M / l;
66 int clim = min(cn, cm);
67 int cl = 1;
68 while(cl <= clim){
69 int cr = min(cn / (cn / cl), cm / (cm / cl));
70 (ans += ((ll)(r + l) * (r - l + 1) / 2 % MOD) * (smu[cr] - smu[cl - 1] + MOD) % MOD * CalF(cn / cl, cm / cl) % MOD) %= MOD;
71 cl = cr + 1;
72 }l = r + 1;
73 }printf("%lld\n", ans);
74 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
75 return 0;
76}
77
78template < typename T >
79inline T read(void){
80 T ret(0);
81 int flag(1);
82 char c = getchar();
83 while(c != '-' && !isdigit(c))c = getchar();
84 if(c == '-')flag = -1, c = getchar();
85 while(isdigit(c)){
86 ret *= 10;
87 ret += int(c - '0');
88 c = getchar();
89 }
90 ret *= flag;
91 return ret;
92}
感觉莫反的题都没什么可说的,基本上就是各种推导的套路然后各种预处理即可。
xxxxxxxxxx
851
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29int A, B, C;
30ll ans(0);
31ll mu[LIM + 100], smu[LIM + 100];
32ll G[LIM + 100][LIM + 100];
33bitset < LIM + 100 > notPrime;
34basic_string < int > Prime;
35
36ll qpow(ll a, ll b){
37 ll ret(1), mul(a);
38 while(b){
39 if(b & 1)ret = ret * mul % MOD;
40 b >>= 1;
41 mul = mul * mul % MOD;
42 }return ret;
43}
44
45int main(){mu[1] = 1;
46 for(int i = 2; i <= LIM; ++i){
47 if(!notPrime[i])Prime += i, mu[i] = -1;
48 for(auto p : Prime){
49 if((ll)i * p > LIM)break;
50 mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
51 notPrime[i * p] = true;
52 if(i % p == 0)break;
53 }
54 }
55 for(int x = 1; x <= LIM; ++x)for(int i = 1; i <= LIM; ++i){
56 if(__gcd(x, i) != 1)continue;
57 for(int y = i; y <= LIM; y += i)(++G[x][y]) %= MOD;
58 }
59 for(int x = 1; x <= LIM; ++x)for(int y = 1; y <= LIM; ++y)(G[x][y] += G[x][y - 1]) %= MOD;
60 A = read(), B = read(), C = read();
61 for(int x = 1; x <= A; ++x)
62 for(int d = 1; d <= min(B, C); ++d){
63 if(__gcd(x, d) != 1)continue;
64 (ans += A / x * mu[d] % MOD * G[x][B / d] % MOD * G[x][C / d] % MOD) %= MOD;
65 }
66 printf("%lld\n", ans);
67 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68 return 0;
69}
70
71template < typename T >
72inline T read(void){
73 T ret(0);
74 int flag(1);
75 char c = getchar();
76 while(c != '-' && !isdigit(c))c = getchar();
77 if(c == '-')flag = -1, c = getchar();
78 while(isdigit(c)){
79 ret *= 10;
80 ret += int(c - '0');
81 c = getchar();
82 }
83 ret *= flag;
84 return ret;
85}
莫反推式子 + 三元环优化,巨恶心,但是思路还是比较清晰明了的,同时不知道为什么我的程序跑的飞快。。。
xxxxxxxxxx
1381
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29int A, B, C;
30ll mu[LIM + 100], smu[LIM + 100];
31ll fa[LIM + 100], fb[LIM + 100], fc[LIM + 100];
32int val[LIM + 100];
33int deg[LIM + 100];
34bitset < LIM + 100 > vis;
35bitset < LIM + 100 > notPrime;
36basic_string < int > Prime;
37
38struct Edge{
39 Edge* nxt;
40 int to;
41 int val;
42 OPNEW;
43}ed[LIM << 5];
44ROPNEW;
45Edge* head[LIM];
46
47ll qpow(ll a, ll b){
48 ll ret(1), mul(a);
49 while(b){
50 if(b & 1)ret = ret * mul % MOD;
51 b >>= 1;
52 mul = mul * mul % MOD;
53 }return ret;
54}
55
56int main(){mu[1] = 1;
57 for(int i = 2; i <= LIM; ++i){
58 if(!notPrime[i])Prime += i, mu[i] = -1;
59 for(auto p : Prime){
60 if((ll)i * p > LIM)break;
61 mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
62 notPrime[i * p] = true;
63 if(i % p == 0)break;
64 }
65 }
66 int T = read();
67 while(T--){
68 ll ans(0);
69 A = read(), B = read(), C = read();
70 int mn = min({A, B, C}), mx = max({A, B, C});
71 memset(fa, 0, sizeof fa), memset(fb, 0, sizeof fb), memset(fc, 0, sizeof fc);
72 memset(deg, 0, sizeof deg), memset(head, 0, sizeof head);
73 for(int i = 1; i <= A; ++i)
74 for(int j = i; j <= mx; j += i)(fa[i] += A / j) %= MOD;
75 for(int i = 1; i <= B; ++i)
76 for(int j = i; j <= mx; j += i)(fb[i] += B / j) %= MOD;
77 for(int i = 1; i <= C; ++i)
78 for(int j = i; j <= mx; j += i)(fc[i] += C / j) %= MOD;
79 for(int i = 1; i <= mn; ++i)(ans += fa[i] * fb[i] * fc[i] * mu[i] * mu[i] * mu[i]) %= MOD;
80 struct Edg{int s, t, v;}; basic_string < Edg > edgs;
81 for(int g = 1; g <= mn; ++g){
82 for(int i = 1; (ll)i * g <= mx; ++i){
83 if(!mu[i * g])continue;
84 for(int j = i + 1; (ll)i * j * g <= mx; ++j){
85 if(!mu[j * g] || __gcd(i, j) != 1)continue;
86 int s = i * g, t = j * g, lcm = i * j * g;
87 (ans += ((mu[s] * mu[s] * mu[t] * ((fa[s] * fb[lcm] * fc[lcm] + fa[lcm] * fb[s] * fc[lcm] + fa[lcm] * fb[lcm] * fc[s]) % MOD)) + MOD) % MOD) %= MOD;
88 (ans += ((mu[s] * mu[t] * mu[t] * ((fa[t] * fb[lcm] * fc[lcm] + fa[lcm] * fb[t] * fc[lcm] + fa[lcm] * fb[lcm] * fc[t]) % MOD)) + MOD) % MOD) %= MOD;
89 ++deg[s], ++deg[t];
90 edgs += {s, t, lcm};
91 // head[s] = new Edge{head[s], t, lcm};
92 // head[t] = new Edge{head[t], s, lcm};
93 }
94 }
95 }
96 for(auto edg : edgs){
97 auto [s, t, v] = edg;
98 if(deg[s] < deg[t] || (deg[s] == deg[t] && s > t))swap(s, t);
99 head[s] = new Edge{head[s], t, v};
100 }
101 for(int s = 1; s <= mx; ++s){
102 if(!mu[s])continue;
103 // vis.reset();
104 // memset(val, 0, sizeof val);
105 for(auto i = head[s]; i; i = i->nxt)vis[SON] = true, val[SON] = i->val;
106 for(auto i = head[s]; i; i = i->nxt){
107 if(!mu[SON])continue;
108 for(auto j = head[SON]; j; j = j->nxt){
109 if(!vis[j->to] || !mu[j->to])continue;
110 (ans += mu[s] * mu[SON] * mu[j->to] * (
111 fa[val[j->to]] * fb[j->val] * fc[i->val] + fa[val[j->to]] * fb[i->val] * fc[j->val] +
112 fa[j->val] * fb[val[j->to]] * fc[i->val] + fa[j->val] * fb[i->val] * fc[val[j->to]] +
113 fa[i->val] * fb[val[j->to]] * fc[j->val] + fa[i->val] * fb[j->val] * fc[val[j->to]]
114 ) % MOD) %= MOD;
115 }
116 }
117 for(auto i = head[s]; i; i = i->nxt)vis[SON] = false, val[SON] = 0;
118 }printf("%lld\n", (ans % MOD + MOD) % MOD);
119 }
120 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
121 return 0;
122}
123
124template < typename T >
125inline T read(void){
126 T ret(0);
127 int flag(1);
128 char c = getchar();
129 while(c != '-' && !isdigit(c))c = getchar();
130 if(c == '-')flag = -1, c = getchar();
131 while(isdigit(c)){
132 ret *= 10;
133 ret += int(c - '0');
134 c = getchar();
135 }
136 ret *= flag;
137 return ret;
138}
依然还是莫反然后推式子,不想帖式子,好像也就没什么可写的了。。。
xxxxxxxxxx
951
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29int N, M;
30ll ans(0);
31ll mu[LIM + 100], smu[LIM + 100];
32ll F[LIM + 100], invF[LIM + 100];
33ll G[LIM + 100], mulG[LIM + 100], invmulG[LIM + 100];
34bitset < LIM + 100 > notPrime;
35basic_string < int > Prime;
36
37ll qpow(ll a, ll b){
38 ll ret(1), mul(a);
39 while(b){
40 if(b & 1)ret = ret * mul % MOD;
41 b >>= 1;
42 mul = mul * mul % MOD;
43 }return ret;
44}
45
46int main(){mu[1] = 1;
47 for(int i = 2; i <= LIM; ++i){
48 if(!notPrime[i])Prime += i, mu[i] = -1;
49 for(auto p : Prime){
50 if((ll)i * p > LIM)break;
51 mu[i * p] = i % p == 0 ? 0 : mu[i] * mu[p];
52 notPrime[i * p] = true;
53 if(i % p == 0)break;
54 }
55 }
56 F[0] = 0, F[1] = 1;
57 for(int i = 2; i <= LIM; ++i)F[i] = (F[i - 1] + F[i - 2]) % MOD;
58 for(int i = 1; i <= LIM; ++i)invF[i] = qpow(F[i], MOD - 2);
59 for(int i = 0; i <= LIM; ++i)G[i] = 1;
60 for(int i = 1; i <= LIM; ++i)
61 for(int j = i; j <= LIM; j += i)
62 (G[j] *= mu[j / i] == 1 ? F[i] : (mu[j / i] == 0 ? 1 : invF[i])) %= MOD;
63 mulG[0] = invmulG[0] = 1;
64 for(int i = 1; i <= LIM; ++i)mulG[i] = mulG[i - 1] * G[i] % MOD, invmulG[i] = qpow(mulG[i], MOD - 2);
65 int T = read();
66 while(T--){
67 ans = 1;
68 N = read(), M = read();
69 int lim = min(N, M);
70 int l = 1;
71 while(l <= lim){
72 int r = min(N / (N / l), M / (M / l));
73 (ans *= qpow(mulG[r] * invmulG[l - 1] % MOD, (ll)(N / l) * (M / l))) %= MOD;
74 l = r + 1;
75 }printf("%lld\n", ans);
76 }
77 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
78 return 0;
79}
80
81template < typename T >
82inline T read(void){
83 T ret(0);
84 int flag(1);
85 char c = getchar();
86 while(c != '-' && !isdigit(c))c = getchar();
87 if(c == '-')flag = -1, c = getchar();
88 while(isdigit(c)){
89 ret *= 10;
90 ret += int(c - '0');
91 c = getchar();
92 }
93 ret *= flag;
94 return ret;
95}
update-2023_03_08 初稿