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$。

结论：

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

设$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

/*
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

/*
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

/*
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

/*
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

/*
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

/*
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;
}

A

B

C

D

E

F

Code

A

B

C

D

E

F

添加新评论

最新文章

最近回复

分类

归档

其它