给定序列,求序列有多少个排列满足任意相邻两数之积非完全平方数。
赛时最终想到的是质因数分解后,两数合成之后若所有质因数幂次均为偶数则为完全平方数,依此可以 next_permutation()
。期望
xxxxxxxxxx
891
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;
30int A[310];
31struct Fact{int val, cnt;};
32basic_string < Fact > facts[310];
33basic_string < int > legal[310];
34bitset < LIM + 100 > notPrime;
35basic_string < int > Prime;
36
37
38int main(){
39 freopen("square.in", "r", stdin);
40 freopen("square.out", "w", stdout);
41 N = read();
42 // for(int i = 2; i <= LIM; ++i){
43 // if(!notPrime[i])Prime += i;
44 // for(auto p : Prime){
45 // if((ll)i * p > LIM)break;
46 // notPrime[i * p] = true;
47 // if(i % p == 0)break;
48 // }
49 // }
50 for(int i = 1; i <= N; ++i){
51 int val = A[i] = read();
52 // for(auto p : Prime){
53 // if((ll)p * p > val)break;
54 // if(val % p == 0)facts[i] += Fact{p, 0};
55 // while(val % p == 0)facts[i].back().cnt++, val /= p;
56 // }if(val != 1)facts[i] += Fact{val, 1};
57 }
58 int ans(0);
59 int base(1);
60 for(int i = 1; i <= N; ++i)base *= i;
61 for(int i = 1; i <= base; ++i){
62 bool flag(true);
63 for(int j = 1; j < N; ++j){
64 ll val = (ll)A[j] * A[j + 1];
65 if((ll)sqrt(val) * (ll)sqrt(val) == val){flag = false; break;}
66 }if(flag)++ans;
67 next_permutation(A + 1, A + N + 1);
68 }printf("%d\n", ans);
69
70
71 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72 return 0;
73}
74
75template < typename T >
76inline T read(void){
77 T ret(0);
78 int flag(1);
79 char c = getchar();
80 while(c != '-' && !isdigit(c))c = getchar();
81 if(c == '-')flag = -1, c = getchar();
82 while(isdigit(c)){
83 ret *= 10;
84 ret += int(c - '0');
85 c = getchar();
86 }
87 ret *= flag;
88 return ret;
89}
CF819D Mister B and Astronomers。
存在一个星星每
一道十分高妙的
xxxxxxxxxx
691
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, T;
29int A[210000];
30ll sumA(0);
31int ans[210000];
32unordered_map < ll, int > equiv;
33
34int main(){
35 freopen("moon.in", "r", stdin);
36 freopen("moon.out", "w", stdout);
37 T = read(), N = read();
38 for(int i = 1; i <= N; ++i)sumA += (A[i] = read());
39 equiv[0] = 1;
40 int curs(0);
41 for(int i = 2; i <= N; ++i)curs += A[i], equiv[curs] = i;
42 double clock_lim = 2.0 / (double)T;
43 for(int t = 0; t <= T - 1; ++t){
44 double sc = (double)clock() / CLOCKS_PER_SEC;
45 int cur(t % sumA);
46 while(equiv.find(cur) == equiv.end() && (double)clock() / CLOCKS_PER_SEC - sc <= clock_lim)(cur += T) %= sumA;
47 if(equiv.find(cur) != equiv.end())ans[equiv[cur]]++;
48 }
49 for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
50
51 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52 return 0;
53}
54
55template < typename T >
56inline T read(void){
57 T ret(0);
58 int flag(1);
59 char c = getchar();
60 while(c != '-' && !isdigit(c))c = getchar();
61 if(c == '-')flag = -1, c = getchar();
62 while(isdigit(c)){
63 ret *= 10;
64 ret += int(c - '0');
65 c = getchar();
66 }
67 ret *= flag;
68 return ret;
69}
没找到原题。
大概就是存在一个一维空间,最小位置在
部分分给的还行,前
xxxxxxxxxx
1151
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, M, Q;
29
30// class SegTree{
31// private:
32// int cnt[110000 << 2];
33// int sum[110000 << 2];
34// int lz[110000 << 2];
35// #define LS (p << 1)
36// #define RS (LS | 1)
37// #define MID ((gl + gr) >> 1)
38// public:
39// void Pushup(int p){
40// sum[p] = sum[LS] + sum[RS];
41// cnt[p] = cnt[LS] + cnt[RS];
42// }
43// void Pushdown(int p){
44// if(!lz[p])return;
45
46// }
47// }
48
49struct Sline{
50 int l, r;
51 friend const bool operator < (const Sline &a, const Sline &b){
52 return a.l == b.l ? a.r < b.r : a.l < b.l;
53 }
54}s[110000];
55
56int main(){
57 freopen("snail.in", "r", stdin);
58 freopen("snail.out", "w", stdout);
59 N = read(), M = read();
60 for(int i = 1; i <= M; ++i)s[i].l = read(), s[i].r = read();
61 sort(s + 1, s + M + 1);
62 Q = read();
63 if((ll)M * Q <= (ll)(1e8)){
64 while(Q--){
65 int l = read(), r = read();
66 int curl = l, curr = l;
67 for(int i = 1; i <= M; ++i)
68 if(curl <= s[i].l && s[i].l <= curr && s[i].r <= r)curr = max(curr, s[i].r);
69 printf("%d\n", curr);
70 }
71 }else{
72 bool spLine(true);
73 for(int i = 1; i <= M - 1; ++i)
74 if(s[i].l < s[i + 1].l && s[i + 1].l < s[i].r){spLine = false; break;}
75 if(spLine){
76 basic_string < int > ans[110000];
77 for(int i = M; i >= 1; --i){
78 ans[s[i].l] += s[i].r;
79 }
80 for(int i = N; i >= 1; --i){
81 basic_string < int > tmp = ans[i];
82 for(auto v : tmp)ans[i] += ans[v];
83 }
84 while(Q--){
85 int l = read(), r = read();
86 int anss(l);
87 for(auto v : ans[l])if(v <= r)anss = max(anss, v);
88 printf("%d\n", anss);
89 // for(int i = 1; i <= M; ++i)
90 // if(curl <= s[i].l && s[i].l <= curr && s[i].r <= r)curr = max(curr, s[i].r);
91 // printf("%d\n", curr);
92 }
93 }
94 }
95
96
97 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
98 return 0;
99}
100
101template < typename T >
102inline T read(void){
103 T ret(0);
104 int flag(1);
105 char c = getchar();
106 while(c != '-' && !isdigit(c))c = getchar();
107 if(c == '-')flag = -1, c = getchar();
108 while(isdigit(c)){
109 ret *= 10;
110 ret += int(c - '0');
111 c = getchar();
112 }
113 ret *= flag;
114 return ret;
115}
首先有一个更高妙的转换,可以认为
存在朴素 DP,考虑按序添加数(这个东西怎么处理赛时属实是想了好久假了好久),不难发现添加
显然处理排列时原序列不同顺序本质相同,于是考虑将原序列排序,依次处理
同时令
对于第三种情况,同理:
对于第四种情况,同理:
同时这里我们注意一个问题,当
最终答案显然为
双倍经验 LG-P4448 [AHOI2018初中组]球球的排列。
xxxxxxxxxx
911
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;
30ll A[310];
31ll s[310];
32ll dp[2][310][310];
33bitset < LIM + 100 > notPrime;
34basic_string < int > Prime;
35
36int main(){
37 for(int i = 2; i <= LIM; ++i){
38 if(!notPrime[i])Prime += i;
39 for(auto p : Prime){
40 if((ll)i * p > LIM)break;
41 notPrime[i * p] = true;
42 if(i % p == 0)break;
43 }
44 }
45 N = read();
46 for(int i = 1; i <= N; ++i){
47 A[i] = read();
48 for(auto p : Prime){
49 if((ll)p * p > A[i])break;
50 while(A[i] % (ll)(p * p) == 0)A[i] /= (ll)p * p;
51 }
52 }
53 sort(A + 1, A + N + 1);
54 int cnt(0);
55 for(int i = 1; i < N; ++i)
56 if(A[i] != A[i + 1])s[i] = 0, cnt = 0;
57 else s[i] = ++cnt;
58 dp[0][0][0] = 1; bool cur(0);
59 for(int i = 0; i < N; ++i){
60 memset(dp[cur ^ 1], 0, sizeof dp[cur ^ 1]);
61 if(A[i] != A[i + 1])
62 for(int j = 0; j <= N; ++j)
63 for(int k = 1; k <= N; ++k)
64 if(j + k <= N)(dp[cur][j + k][0] += dp[cur][j][k]) %= MOD, dp[cur][j][k] = 0;
65 for(int j = 0; j <= N; ++j)
66 for(int k = 0; k <= N; ++k){
67 if(2 * s[i] - k > 0)(dp[cur ^ 1][j][k + 1] += dp[cur][j][k] * (2 * s[i] - k) % MOD) %= MOD;
68 if(j - 1 >= 0)(dp[cur ^ 1][j - 1][k] += dp[cur][j][k] * j % MOD) %= MOD;
69 if(i + 1 - (2 * s[i] - k) - j >= 0)(dp[cur ^ 1][j][k] += dp[cur][j][k] * (i + 1 - (2 * s[i] - k) - j) % MOD) %= MOD;
70 }
71 cur ^= 1;
72 }printf("%lld\n", dp[cur][0][0]);
73 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74 return 0;
75}
76
77template < typename T >
78inline T read(void){
79 T ret(0);
80 int flag(1);
81 char c = getchar();
82 while(c != '-' && !isdigit(c))c = getchar();
83 if(c == '-')flag = -1, c = getchar();
84 while(isdigit(c)){
85 ret *= 10;
86 ret += int(c - '0');
87 c = getchar();
88 }
89 ret *= flag;
90 return ret;
91}
首先不难想到,令
对于后者式子不难发现其为经典的群论套路,即我们发现对于某个科学家的初始点
显然我们要证明的即为如下式子:
证明均显然。
此时我们考虑,对于一个环内的所有科学家,
所以我们可以考虑对于一个环内的所有科学家
转化后得到:
并且显然满足
现在我们在将目光移回上文所述的排序过程,考虑发现该限制对应到上述方程的意义就是
最终复杂度卡在排序和两次 exgcd 上,为
Tips:还有些小细节,观察所有式子发现,对于所有 set
中排除同环模意义下同位置的,可以考虑利用 C++ 特性,重载小于号,使得只保留相同第一关键字中最先加入的,可以证明最先加入的一定最小。
附:好久没写 exgcd 了,简单重推一下吧:
要求
显然存在
又
整理并展开
则显然有
问题规模缩减,不断递归,直到最终
此时得到任意解,令
xxxxxxxxxx
901
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 N;
27ll S, T;
28int A[210000];
29int ans[210000];
30int gcdv(-1);
31struct Node{
32 ll v; ll origin; int idx;
33 friend const bool operator < (const Node &a, const Node &b){
34 return a.v < b.v;
35 }
36};
37unordered_map < int, set < Node > > loops;
38
39void exgcd(ll a, ll b, ll &x, ll &y){
40 if(!b)return x = 1, y = 0, void();
41 exgcd(b, a % b, x, y);
42 int tmp(x);
43 x = y, y = tmp - a / b * y;
44}
45ll CalMnX(ll ti, ll tj){
46 ll x, y; ll d = (tj - ti) / gcdv;
47 exgcd(S, T, x, y);
48 x *= d, y *= d;
49 ll P = T / gcdv;
50 x = (x % P + P) % P;
51 y = (tj - ti - S * x) / T;
52 return x;
53}
54
55int main(){
56 T = read(), N = read();
57 for(int i = 1; i <= N; ++i)(S += (A[i] = read())) %= T;
58 gcdv = __gcd(S, T);
59 loops[0].insert({Node{0, 0, 1}});
60 ll cur(0);
61 for(int i = 2; i <= N; ++i)
62 (cur += A[i]) %= T,
63 loops[cur % gcdv].insert(Node{CalMnX(cur % gcdv, cur), cur, i});
64 for(auto loop : loops){
65 if((int)loop.second.size() == 1){ans[loop.second.begin()->idx] = T / gcdv; continue;}
66 for(auto it = loop.second.begin(); it != loop.second.end(); advance(it, 1)){
67 auto nxit = it == prev(loop.second.end()) ? loop.second.begin() : next(it);
68 ans[it->idx] = CalMnX(it->origin, nxit->origin);
69 }
70 }
71 for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
72 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
73 return 0;
74}
75
76template < typename T >
77inline T read(void){
78 T ret(0);
79 int flag(1);
80 char c = getchar();
81 while(c != '-' && !isdigit(c))c = getchar();
82 if(c == '-')flag = -1, c = getchar();
83 while(isdigit(c)){
84 ret *= 10;
85 ret += int(c - '0');
86 c = getchar();
87 }
88 ret *= flag;
89 return ret;
90}
首先记录一下 @sssmzy 的部分分做法:
对于传送门无重叠,加个倍增即可保证复杂度。
对于询问无重叠,考虑暴力建图即可均摊正确复杂度。
正解分块或吉司机线段树。
//TODO (先去学吉司机线段树了。。
update-2023_02_13 初稿