AGC005

link

A

给定一个仅由ST构成的串X。执行如下操作$10^{10000}$次:

如果X包含ST子串,就把第一个ST子串删掉。

直接用一个栈模拟就可以了。

B

给定一个序列$a_1\dots a_n$。

求$\sum_{1\le l\le r\le n}\min_{l\le i\le r}a_i$。

枚举这个$\min a_i$,

那么答案就是求$\sum_{x}x\sum_{1\le l\le r\le n}[\min_{l\le i\le r}a_i = x]$。

显然对于所有$\sum_{1\le l\le r\le n}[\min_{l\le i\le r}a_i = x]>0$的$x$存在$i$使得$x=a_i$。

如果$a_i\not=a_j$,那么$[\min_{l\le i\le r}a_i = a_x]$当且仅当$l\le x\le r$且$\forall _{l\le i\le r}a_i\ge a_x$。

枚举$a_i$,然后$a_j<a_i$的所有$j$都不能包含在区间内。找到$j_1=j<i$的最大$j$,和$j_2=j>i$的最小$j$。那满足条件的区间数就是$(j_2-i)(i-j_1)$。

怎么找到$j_1,j_2$呢?从小到大枚举,然后枚举完以后扔进set表示不能选择。

如果$a_i$可以$=a_j$,那怎么办?

这种情况直接随机顺序然后按照上面说的set维护也是可以的。

时间复杂度$O(n\log n)$。

C

给定$a_1\dots a_n$,判断是否存在一棵树满足第$i$个点离最远点的距离为$a_i$。

结论:

  1. 每个点的最远点都在一条直径的一个端点上。
  2. 如果直径长度为偶数,所有直径交于一点。
  3. 如果直径长度为奇数,所有直径交于一边。

设$b_x=\sum [a_i=x],m=\max a_i$。

那么存在一棵树当且仅当:

m是奇数:

$$
b_1\dots b_{\lfloor \frac{m}{2}\rfloor}=0\\
b_{\lceil \frac{m}{2}\rceil}=2\\
b_{\lceil \frac{m}{2}\rceil+1}\dots b_m\ge 2
$$

m是偶数:

$$
b_1\dots b_{\frac{m}{2}-1}=0\\
b_{\frac{m}{2}}=1\\
b_{\frac{m}{2}+1}\dots b_m\ge 2
$$

D

给定$n,k$,求有多少个排列$a_1\dots a_n$满足$|a_i-i|\not=k$。

建一个二分图,令$X_i$匹配$Y_j$等价于$a_i=j$。

若$|i-j|=k$,那么$X_i$向$Y_j$连一条红边,否则连一条蓝边。

则原问题等价于求全是蓝边的完美匹配数。

经典容斥:$ans=\sum_{i=0}^n(-1)^i(n-i)!b_i$,其中$b_i$表示匹配$i$条红边的方案数。

实际上如果只考虑红边,那么形成了一些链。

那就把链给抽出来。分别DP然后背包合并。

E

有$n$个点,n-1条红边n-1条蓝边,分别构成了一棵红树和一棵蓝树。

一开始A在X点,B在Y点。

从A开始,每个人可以进行一次操作:

不动或者选一条边走到另一端,其中A只能走红边,B只能走蓝边。

若A,B相遇则结束。A希望轮数最多。B希望轮数最少。求最终轮数。

如果存在一条红边,它两端在蓝树上距离>2,那么如果A能安全到达其中一段,就永远不会结束。

否则?

考虑从A开始BFS。如果一个点离A的距离$\le$离B的距离,那么A到达这个点后(或者到达之前)B一定可以让游戏结束了

否则可以继续从这个点BFS。

然后最优的策略显然就是去到能到达的离B最远的点然后不动了。

F

有一棵树,对于$k=1\dots n$, 求出对于在$n$个点选出$k$个点这$\binom{n}{k}$种方案,包含这些点的最小联通块的点数的和。

显然这个联通块点数=边数+1。那么我们只需要算出边数和$+\binom{n}{k}$。

边数和又可以拆成每一条边出现次数的和。

一条边出现显然当且仅当两边都有被选出的点。那么对于一条边的出现次数,假设一边点数是$x$,显然可以容斥:

$cnt=\binom{n}{k}-\binom{x}{k}-\binom{n-x}{k}$。

这样可以$O(n^2)$算了。

显然是不够的。

除了$\binom{n}{k}$以外,记$-\binom{x}{k}$的出现次数为$a_x$,

那么答案就是$ans_k=n\binom{n}{k}-\sum_{x}a_x\binom{x}{k}$。

记$c_k=\sum_{x}a_x\binom{x}{k}\Leftrightarrow c_kk!=\sum_{x}a_xx!\frac{1}{(x-k)!}$

设$A_k=A_kk!,B_k=\frac{1}{(n-k)!}$,那么$c_kk!=\sum_x A_xB_{n+k-i}$。

若$C_{k+n}=c_{k}k!$,那就直接$C_{k}=\sum_x A_xB_{k-x}$。直接NTT!原根是5!

Code

A

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
char stk[200005],s[200005];
int t;
void add(char c){
if(!t||c=='S'||stk[t]!='S')stk[++t]=c;
else --t;
}
int main(){
#ifdef QAQAutoMaton
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%s",s);
for(char *a=s;*a;++a)add(*a);
write(t,'\n');
return 0;
}

B

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll a[200005],b[200005];
set<ll> f;
int main(){
#ifdef QAQAutoMaton
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
ll n;
read(n);
for(ll i=1;i<=n;++i){
read(a[i]);
b[a[i]]=i;
}
f.insert(0);
f.insert(n+1);
ll ans=0,s;
for(ll i=1;i<=n;++i){
set<ll>::iterator a=f.lower_bound(b[i]);
s=*a-b[i];
--a;
s*=(b[i]-*a);
ans+=s*i;
f.insert(b[i]);
}
write(ans,'\n');
return 0;
}

C

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[200005],b[200005];
void check(bool a){
if(!a){write("Impossible\n");exit(0);}
}
int main(){
#ifdef QAQAutoMaton
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
int n;
read(n);
for(int i=1;i<=n;++i){
read(a[i]);
check(a[i]<=n);
++b[a[i]];
}
sort(a+1,a+n+1);
int s=a[n];
if(!(s&1)){
check(a[1]==s>>1);
check(b[s>>1]==1);
int x=0;
for(int i=s;i>s>>1;--i)check(b[i]>1);
write("Possible\n");
}
else{
int t=(s+1)>>1;
check(a[1]==t);
check(b[t]==2);
int x=0;
for(int i=s;i>t;--i)check(b[i]>1);
write("Possible\n");
}
return 0;
}

D

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
/*
Author: QAQ-Automaton
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
const ll p=924844033;
ll f[4047][4047][2],dp[2047],ndp[2047],fac[2047];
int main(){
#ifdef QAQAutoMaton
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
ll n,k;
read(n,k);
f[0][0][0]=f[0][0][1]=1;
for(ll i=1;i<=n;++i){
f[i][0][0]=f[i][0][1]=1;
for(ll j=1;j<=i;++j){
f[i][j][0]=f[i-1][j][1];
f[i][j][1]=(f[i-1][j-1][0]+f[i][j][0])%p;
}
}
dp[0]=1;
for(ll i=1;i<=k;++i){
ll m=(n-i)/k;
for(ll j=0;j<=m;++j){
for(ll k=j;k<=n;++k){
ndp[k]=(ndp[k]+dp[k-j]*f[m][j][1])%p;
}
}
for(ll k=0;k<=n;++k){dp[k]=ndp[k];ndp[k]=0;}
for(ll j=0;j<=m;++j){
for(ll k=j;k<=n;++k){
ndp[k]=(ndp[k]+dp[k-j]*f[m][j][1])%p;
}
}
for(ll k=0;k<=n;++k){dp[k]=ndp[k];ndp[k]=0;}

}
//for(ll i=0;i<=n;++i)write(dp[i],i==n?'\n':' ');
fac[0]=fac[1]=1;
for(ll i=2;i<=n;++i)fac[i]=fac[i-1]*i%p;
ll ans=0;
for(ll i=0;i<=n;++i){
ans=(ans+fac[n-i]*dp[i]%p*(i&1?p-1:1))%p;
}
write(ans,'\n');
return 0;
}

E

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
148
149
150
151
152
/*
Author: QAQ-Automaton
LANG: C++
PROG: e.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) #define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int n,x,y;
vector<int> R[200005],B[200005];
int loop[200005],dfn[200005],low[200005],t,dis[200005],fa[200005],Dis[200005],Fa[200005];
void BlueDFS(int x,int f){
fa[x]=f;
dfn[x]=++t;
dis[x]=dis[f]+1;
for(auto i:B[x])if(i!=f)BlueDFS(i,x);
low[x]=++t;
}
int chk(int x,int y){
if(dfn[x]>dfn[y])swap(x,y);
if(dfn[x]<=dfn[y] && low[y]<=low[x])return dis[y]-dis[x]>2;
return fa[x]!=fa[y];
}
int q[200005],*l,*r;
int RedBFS(int x){
*(l=r=q)=x;
int ans=dis[x]<<1;
if(loop[x])return -1;
while(l<=r){
for(auto i:R[*l])if(i!=Fa[*l]){
Fa[i]=*l;
Dis[i]=Dis[*l]+1;
if(Dis[i]>dis[i])continue;
else chkmax(ans,dis[i]<<1);
if(Dis[i]<dis[i]){
*(++r)=i;
if(loop[i])return -1;
}
}
++l;
}
return ans;
}
int main(){
#ifdef QAQAutoMaton
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
#endif
read(n,x,y);
if(x==y){write("0\n");return 0;}
int u,v;
for(int i=1;i<n;++i){read(u,v);R[u].push_back(v);R[v].push_back(u);}
for(int i=1;i<n;++i){read(u,v);B[u].push_back(v);B[v].push_back(u);}
dis[0]=-1;
BlueDFS(y,0);
for(int i=1;i<=n;++i){
for(auto j:R[i]){
if(chk(i,j)){loop[i]=1;break;}
}
}
write(RedBFS(x),'\n');
return 0;
}

F

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/*
Author: QAQ-Automaton
LANG: C++
PROG: f.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
const ll p=924844033,g=5,ig=554906420;
ll fac[200005],inv[200005],invf[200005],rev[524299];
ll n,u,v;
vector<ll> son[200005];
ll a[524299],b[524299],siz[200005];
void dfs(ll x,ll fa){
siz[x]=1;
for(auto i:son[x])if(i!=fa){dfs(i,x);siz[x]+=siz[i];}
if(fa){
++a[siz[x]];
++a[n-siz[x]];
}
}
ll fpm(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;return c;}
void NTT(ll *a,ll n,ll flg){
for(ll i=1;i<n;++i){
rev[i]=rev[i>>1]>>1 | ((i&1)*(n/2));
if(i<rev[i])swap(a[i],a[rev[i]]);
}

for(ll i=1;i<n;i<<=1){
ll w=fpm(flg==1?g:ig,(p-1)/i/2),ww,u,v;
for(ll j=0;j<n;j+=i+i){
ww=1;
for(ll k=0;k<i;++k){
u=a[j+k];
v=a[j+k+i]*ww%p;
a[j+k]=(u+v)%p;
a[j+k+i]=(u+p-v)%p;
ww=ww*w%p;
}
}
}
if(flg==-1){
ll fg=fpm(n,p-2);
for(ll i=0;i<n;++i)a[i]=a[i]*fg%p;
}
}
int main(){
#ifdef QAQAutoMaton
freopen("f.in","r",stdin);
freopen("f.out","w",stdout);
#endif
read(n);
fac[0]=fac[1]=1;
inv[1]=1;
invf[0]=invf[1]=1;
for(ll i=2;i<=n;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=invf[i-1]*inv[i]%p;
}
for(ll i=1;i<n;++i){
read(u,v);
son[u].push_back(v);
son[v].push_back(u);
}
dfs(1,0);
for(ll i=0;i<=n;++i){
a[i]=a[i]*fac[i]%p;
b[i]=invf[n-i];
}
ll N=1;
for(;N<=n+n;N<<=1);
NTT(a,N,1);
NTT(b,N,1);
for(ll i=0;i<N;++i)a[i]=a[i]*b[i]%p;
NTT(a,N,-1);
for(ll i=1;i<=n;++i){
write((p-a[i+n]*invf[i]%p+n*fac[n]%p*invf[n-i]%p*invf[i])%p,'\n');
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×