AtCoder Beginner Contest 253 Solution更好的阅读体验戳此进入题面链接题面 Luogu 链接依然 abcd 太水了所以跳了[ABC253E] Distance Sequence题面SolutionCode[ABC253F] Operations on a Matrix题面SolutionCode[ABC253G] Swap Many Times题面SolutionCode[ABC253Ex] We Love Forest题面SolutionCodeUPD
给定
一看题意和数据范围,DP 显然,不难想到设状态
同时注意转移前需要判断是否满足
然后按照这个做完会发现 WA 了两个点,具体看一下就会发现,按照这个式子,如果
xxxxxxxxxx
611
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27int N, M, K;
28ll dp[1100][5100];
29ll sum[5100];
30
31int main(){
32 N = read(), M = read(), K = read();
33 for(int i = 1; i <= M; ++i)dp[1][i] = 1, sum[i] = i;
34 for(int i = 2; i <= N; ++i){
35 for(int j = 1; j <= M; ++j){
36 (dp[i][j] += j + K <= M ? (sum[M] - sum[j + K - 1] + MOD) % MOD : 0) %= MOD;
37 (dp[i][j] += j - K >= 1 ? sum[j - K] : 0) %= MOD;
38 if(!K)(dp[i][j] += -(sum[j] - sum[j - 1]) + MOD) %= MOD;
39 }
40 for(int j = 1; j <= M; ++j)
41 sum[j] = (sum[j - 1] + dp[i][j]) % MOD;
42 }printf("%lld\n", sum[M]);
43 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44 return 0;
45}
46
47template < typename T >
48inline T read(void){
49 T ret(0);
50 int flag(1);
51 char c = getchar();
52 while(c != '-' && !isdigit(c))c = getchar();
53 if(c == '-')flag = -1, c = getchar();
54 while(isdigit(c)){
55 ret *= 10;
56 ret += int(c - '0');
57 c = getchar();
58 }
59 ret *= flag;
60 return ret;
61}
存在
1 l r x
:将 2 i x
:将第 3 i j
:输出矩阵 感觉还算是一道细节不少的题。
首先这道题的做法不少,主流的就是类似二位偏序维护,或者写一个区间修改的主席树。
这里主要说一下用 BIT 维护的方法。
首先不难想到,
思路就是这样,维护的方式还是有些高妙的。先考虑离线一遍,然后维护对于每个查询的上一次对应的推平,同时维护该查询的初始值,然后在需要减去的位置开个 basic_string
插进去需要减的序号。然后我们考虑会有一次区间的查询,用 BIT 和前缀和维护,再遍历一次操作,先将前缀加起来,然后减去的那个前缀就在我们第二次遍历的时候通过遍历对应的 basic_string
而减去。然后最后跑一遍输出答案即可。
xxxxxxxxxx
931
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25int N, M, Q;
26int lst[210000], pos[210000];
27ll ans[210000];
28struct Query{int opt; int a, b, c;}qs[210000];
29basic_string < int > del[210000];
30
31class BIT{
32private:
33 ll tr[210000];
34public:
35 int lowbit(int x){return x & -x;}
36 void Modify(int x, int v){while(x <= M)tr[x] += v, x += lowbit(x);}
37 ll Query(int x){ll ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
38 void ModifyRange(int l, int r, ll v){Modify(l, v), Modify(r + 1, -v);}
39}bit;
40
41int main(){
42 // freopen("test_05.txt", "r", stdin);
43 // freopen("out.txt", "w", stdout);
44 N = read(), M = read(), Q = read();
45 for(int i = 1; i <= Q; ++i){
46 int opt = read();
47 switch(opt){
48 case 1:{
49 int l = read(), r = read(), v = read(); qs[i] = Query{opt, l, r, v};
50 break;
51 }
52 case 2:{
53 int p = read(), v = read(); qs[i] = Query{opt, p, v};
54 pos[p] = i;
55 break;
56 }
57 case 3:{
58 int x = read(), y = read(); qs[i] = Query{opt, x, y};
59 ans[i] = qs[pos[x]].b;
60 del[pos[x]] += i;
61 break;
62 }
63 default: break;
64 }
65 }
66 for(int i = 1; i <= Q; ++i){
67 switch(qs[i].opt){
68 case 1:{bit.ModifyRange(qs[i].a, qs[i].b, qs[i].c); break;}
69 case 2:{for(auto p : del[i])ans[p] -= bit.Query(qs[p].b); break;}
70 case 3:{ans[i] += bit.Query(qs[i].b); break;}
71 default: break;
72 }
73 }
74 for(int i = 1; i <= Q; ++i)if(qs[i].opt == 3)printf("%lld\n", ans[i]);
75 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
76 return 0;
77}
78
79template < typename T >
80inline T read(void){
81 T ret(0);
82 int flag(1);
83 char c = getchar();
84 while(c != '-' && !isdigit(c))c = getchar();
85 if(c == '-')flag = -1, c = getchar();
86 while(isdigit(c)){
87 ret *= 10;
88 ret += int(c - '0');
89 c = getchar();
90 }
91 ret *= flag;
92 return ret;
93}
你有一个长度为
然后你可以根据
例如,当
定义一个二元组
给出一个
究极细节怪,大概就是手动模拟一下会发现规律,对于
xxxxxxxxxx
791
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22template < typename T = int >
23inline T read(void);
24
25int N;
26ll L, R;
27ll spl[210000];
28int a[210000];
29int ans[210000];
30
31int main(){
32 N = read(), L = read < ll >(), R = read < ll >();
33 for(int i = 1; i <= N; ++i)a[i] = i;
34 for(int i = 1; i <= N; ++i)spl[i] = spl[i - 1] + N - i;
35 int lp = distance(spl, lower_bound(spl + 1, spl + N + 1, L));
36 int rp = distance(spl, upper_bound(spl + 1, spl + N + 1, R));
37 if(lp == rp){
38 for(ll cur = L; cur <= R; ++cur){
39 int pos = cur - spl[lp - 1];
40 swap(a[lp], a[lp + pos]);
41 }
42 for(int i = 1; i <= N; ++i)printf("%d%c", a[i], i == N ? '\n' : ' ');
43 exit(0);
44 }
45 for(ll cur = L; cur <= spl[lp]; ++cur){
46 int pos = cur - spl[lp - 1];
47 swap(a[lp], a[lp + pos]);
48 }
49 for(int i = 1; i <= lp; ++i)ans[i] = a[i];
50 if(lp + 1 < rp){
51 int s = lp + 1, siz = rp - lp - 1;
52 for(int cnt = 0; s + siz + cnt <= N; ++cnt)ans[s + siz + cnt] = a[s + cnt];
53 for(int cnt = 0; cnt <= siz - 1; ++cnt)ans[s + cnt] = a[N - cnt];
54 }else
55 for(int i = 1; i <= N; ++i)ans[i] = a[i];
56 for(ll cur = spl[rp - 1] + 1; cur <= R; ++cur){
57 int pos = cur - spl[rp - 1];
58 swap(ans[rp], ans[rp + pos]);
59 }
60 for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
61 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
62 return 0;
63}
64
65template < typename T >
66inline T read(void){
67 T ret(0);
68 int flag(1);
69 char c = getchar();
70 while(c != '-' && !isdigit(c))c = getchar();
71 if(c == '-')flag = -1, c = getchar();
72 while(isdigit(c)){
73 ret *= 10;
74 ret += int(c - '0');
75 c = getchar();
76 }
77 ret *= flag;
78 return ret;
79}
给定
考虑 FZT,即子集计数,具体可参考 FZT - 子集计数学习笔记 或 [ABC213G] Connectivity 2 Solution,发现本题与 ABC213G 相似。
因为本题存在选的边数的限制,所以不难想到需要在一般 FZT 的状态中额外添加一维记录。
状态类比 ABC213G,较为显然,令
首先考虑如何处理
然后发现这个东西有重复,不难想到重复分为两种,一种是因为
或:
然后初始值大概是
不难发现如果无脑处理
则预处理
然后矩阵树定理的结论大概就是首先对这个图建出拉普拉斯矩阵
于是考虑如何转移 __builtin_popcount(S)
,不难发现转移:
也就是钦定一个子集为一棵树,然后剩下的作为森林,钦定
不过很遗憾这个又是错的。我们在 ABC213G 中钦定
边界条件的话就是如果
然后考虑答案,令
也不难理解,概率转计数,总方案数为
大概就这样了,处理
xxxxxxxxxx
1051
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29struct Edge{
30 Edge* nxt;
31 int to;
32 OPNEW;
33}ed[1100];
34ROPNEW(ed);
35Edge* head[20];
36
37int N, M;
38int deg[20];
39ll G[MAX_STATUS], F[20][MAX_STATUS];
40int cnte[MAX_STATUS];
41ll fact[30];
42
43int lowbit(int x){return x & -x;}
44int CalCnt(int S, int T){return cnte[S | T] - cnte[S] - cnte[T];}
45ll qpow(ll a, ll b){
46 ll ret(1), mul(a);
47 while(b){
48 if(b & 1)ret = ret * mul % MOD;
49 b >>= 1;
50 mul = mul * mul % MOD;
51 }return ret;
52}
53
54int main(){fact[0] = 1;
55 for(int i = 1; i <= 20; ++i)fact[i] = fact[i - 1] * i % MOD;
56 N = read(), M = read();
57 const int Smx = (1 << N) - 1;
58 for(int i = 1; i <= M; ++i){
59 int s = read(), t = read();
60 head[s] = new Edge{head[s], t};
61 head[t] = new Edge{head[t], s};
62 }
63 for(int S = Smx; S; S = (S - 1) & Smx){
64 int cnt(0);
65 for(int p = 1; p <= N; ++p)
66 for(auto i = head[p]; i; i = i->nxt)
67 if(EXIST(p) && EXIST(SON))++cnt;
68 cnt >>= 1;
69 cnte[S] = cnt;
70 }
71 for(int S = 1; S <= Smx; ++S){
72 if(__builtin_popcount(S) == 1){G[S] = 1; continue;}
73 for(int T = (S - 1) & S; T; T = (T - 1) & S)
74 if(T & lowbit(S))
75 (G[S] += G[T] * G[S ^ T] % MOD * CalCnt(T, S ^ T) % MOD) %= MOD;
76 (G[S] *= qpow(__builtin_popcount(S) - 1, MOD - 2)) %= MOD;
77 }
78 for(int i = 0; i <= N - 1; ++i)
79 for(int S = 0; S <= Smx; ++S){
80 if(__builtin_popcount(S) == i + 1){F[i][S] = G[S]; continue;}
81 for(int T = (S - 1) & S; T; T = (T - 1) & S)
82 if(T & lowbit(S) && i - (__builtin_popcount(T) - 1) >= 0)
83 (F[i][S] += G[T] * F[i - (__builtin_popcount(T) - 1)][S ^ T]) %= MOD;
84 }
85 for(int i = 1; i <= N - 1; ++i)
86 printf("%lld\n", F[i][Smx] * fact[i] % MOD * qpow(qpow(M, i), MOD - 2) % MOD);
87 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88 return 0;
89}
90
91template < typename T >
92inline T read(void){
93 T ret(0);
94 int flag(1);
95 char c = getchar();
96 while(c != '-' && !isdigit(c))c = getchar();
97 if(c == '-')flag = -1, c = getchar();
98 while(isdigit(c)){
99 ret *= 10;
100 ret += int(c - '0');
101 c = getchar();
102 }
103 ret *= flag;
104 return ret;
105}
update-2022_12_07 初稿