Suffering, exploding zero!!

Hey... Topics

prob1: A

Main idea of the title: Two operations: turning a bit over or different or a number in a set on the binary system of a number to find the minimum number of steps from(s) to(t\)

\ (sb) Question, Complete Water Question, Result (bfs) Queue Writing Wilted

The first operation can be converted to the second one, and each number can only be exclusive or once at most, just fool around with (bfs\). But the minimum step updates need to be made when entering the team, and whether updates are made as entry conditions, or they will blow up (don't ask me how I know)

Paste code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;++i)
#define int long long
#define xx 270000
const int mod=998244353;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
int que[xx][3];
int q[xx],all,ans[xx];
inline void bfs()
{
    int head=0,tail=-1;
    que[++tail][0]=0;
    que[tail][1]=0;
    que[tail][2]=0;
    while(head<=tail)
    {
        int w=que[head][0],u=que[head][1],v=que[head++][2];
        fur(i,w+1,all)
        {
            if(!ans[u^q[i]])
            {
                que[++tail][0]=i;
                que[tail][1]=u^q[i];
                ans[u^q[i]]=v+1;
                que[tail][2]=v+1;
            }
        }
    }
}
signed main()
{
    int t=in;
    q[1]=1;
    fur(i,2,18) q[i]=q[i-1]<<1;
    while(t--)
    {
        int n=in,m=in;all=18;
        fur(i,1,n) q[++all]=in;
        int res=0;
        memset(ans,0,sizeof(ans));
        bfs();
        ans[0]=0;
        fur(i,1,m)
        {
            int s=in,tt=in;
            res=(res+i*ans[s^tt]%mod)%mod;
        }
        printf("%lld\n",res);
    }
    return 0;
}

prob2: B

Topic: Given a string of strings (only 26 letters in English), find the shortest non-subsequence strings with the smallest dictionary order.

At first I thought it was a string problem, but later I thought it was a graph topic. How could I not imagine it was a greedy +hard (DP hard) problem (Xuejie hard ah). When the size of the string is less than 26, we can get the answer clearly. Through this nature, we can go back and forth (DP hard):___________

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;++i)
#define fdr(i,a,b) for(int i=a;i>=b;--i)
#define xx 500010
#define inf 0x7fffffff
int f[xx][27],g[xx],pos[xx],n;
char ch[xx];
inline void dfs(int q,int len)
{
    if(len==1)
    {
        fur(i,1,26)
        {
            if(f[q][i]==n+1)
            {
                printf("%c",i+'a'-1);
                return;
            }
        }
    }
    fur(i,1,26)
    {
        if(g[f[q][i]]==len)
        {
            printf("%c",i+'a'-1);
            dfs(f[q][i]+1,len-1);
            break;
        }
    }
}
int main()
{
    scanf("%s",ch+1);
    n=strlen(ch+1);
    fur(i,1,26) f[n+1][i]=n+1,pos[i]=n+1;
    g[n+1]=1;
    fdr(i,n,1)
    {
        fur(j,1,26) f[i][j]=f[i+1][j];
        f[i][ch[i]-'a'+1]=i;
        g[i]=inf;
        fur(j,1,26) g[i]=min(g[i],g[pos[j]]+1);
        pos[ch[i]-'a'+1]=i;
    }
    int ans=inf;
    fur(i,1,26)
    {
        if(f[1][i]==n+1)
        {
            printf("%c\n",i+'a'-1);
            return 0;
        }
        ans=min(ans,g[f[1][i]]);
    }
    dfs(1,ans);
    printf("\n");
    return 0;
}

prb3: C

Main idea of the title: Given the (n*m) matrix, find the number of three-point-to-three-point collinear schemes

I don't want to say anything because I made a mistake in the exam.

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;++i)
#define int long long
const int xx=1e7+10;
const int n6=166666668;
const int mod=1e9+7;
int phi[xx],prime[xx],cnt=0,ans=0,m,n;
bool mark[xx];
inline void handle()
{
    phi[1]=1;
    fur(i,2,n)
    {
        if(!mark[i]) phi[i]=i-1,prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=n;++j)
        {
            mark[i*prime[j]]=true;
            if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}
inline int calc(int x,int d,int u){return (x-u*d+x-d)*u/2%mod;}
inline int C(int nm){return nm*(nm-1)%mod*(nm-2)%mod*n6%mod;}
signed main()
{
    scanf("%lld%lld",&n,&m);
    if(n>m) swap(n,m);
    --n;--m;
    handle();
    fur(i,1,n)
    {
        int tmp=phi[i];
        tmp=(tmp*calc(n+1,i,n/i))%mod;
        tmp=(tmp*calc(m+1,i,m/i))%mod;
        ans=(ans+tmp)%mod;
    }
    ans=(ans-((n+1)*n/2%mod)*((m+1)*m/2%mod)%mod+mod)%mod;
    ans=(ans<<1)%mod;
    ans=(ans+(n+1)*C(m+1)%mod+(m+1)*C(n+1)%mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

prob4: D

Main idea: Given an arbitrary graph composed of (n) labeled nodes, find the sum of the (k) power of the number of trees in the graph.

Knowledge Reserve: The Second Kind of Stirling Number+prufer Sequence

And the class mood is not good, and did not listen carefully, leading to this problem will not, the scale is not understood, directly \\\\\\\\\\

(This crushing is disgusting):

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
#define N 50005
using namespace std;

const int mo=998244353,G=3;
int n,K,rev[N*3],len,num,g[25][N];
LL S[25][25],jc[N],ny[N],wn[50],f[N*3],h[N*3],ans;

LL qp(LL x,LL y) {
    LL res=1;
    for(;y;y>>=1ll,x=x*x%mo)
        if(y&1ll) res=res*x%mo;
    return res;
}
void pre() {
    jc[0]=ny[0]=1;
    for(int i=1;i<=n;++i) jc[i]=jc[i-1]*i%mo;
    ny[n]=qp(jc[n],mo-2);
    for(int i=n-1;i>=0;--i) ny[i]=ny[i+1]*(i+1)%mo;
    f[1]=1*ny[0];
    for(int i=2;i<=n;++i) f[i]=qp(i,i-2)*ny[i-1]%mo;
    S[0][0]=1;
    for(int i=1;i<=K;++i)
        for(int j=1;j<=i;++j)
            S[i][j]=(S[i-1][j]*j%mo+S[i-1][j-1])%mo;
    for(len=1,num=0;len<=n+n;len<<=1,num++);
    for(int i=1;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(num-1));
    for(int i=0;i<=45;++i) wn[i]=qp(G,(mo-1)/(1<<i));
}
void ntt(LL *x,int sign) {
    for(int i=0;i<len;++i) if(i<rev[i]) swap(x[i],x[rev[i]]);
    for(int k=2,e=1;k<=len;k<<=1,e++) {
        for(int i=0;i<len;i+=k) {
            LL *a=x+i,*b=x+i+(k>>1); LL u,v,w=1;
            for(int j=0;j<(k>>1);++j,w=w*wn[e]%mo) {
                u=a[j],v=b[j]*w%mo;
                a[j]=u+v; a[j]>=mo?a[j]-=mo:0;
                b[j]=u-v; b[j]<0?b[j]+=mo:0;
            }
        }
    }
    if(sign==-1) {
        int inv=qp(len,mo-2);
        for(int i=0;i<len;++i) x[i]=x[i]*inv%mo;
        reverse(x+1,x+len);
    }
}
LL C(LL x,LL y) {return x>=y?jc[x]*ny[y]%mo*ny[x-y]%mo:0;}
int main()
{
    scanf("%d%d",&n,&K);
    pre();
    g[0][0]=1; ntt(f,1);
    for(int i=1;i<=K;++i) {
        memset(h,0,sizeof(h[0])*len);
        for(int j=0;j<=n;++j) h[j]=1ll*g[i-1][j]*ny[j]%mo;
        ntt(h,1);
        for(int j=0;j<len;++j) h[j]=h[j]*f[j]%mo;
        ntt(h,-1);
        for(int j=1;j<=n;++j) g[i][j]=h[j]*jc[j-1]%mo;
    }
    for(int i=1;i<=n;++i) {
        LL tmp=qp(2,1ll*(n-i)*(n-i-1)/2ll)*C(n,i)%mo;
        for(int j=1;j<=K;++j) {
            ans+=g[j][i]*S[K][j]%mo*jc[j]%mo*tmp%mo;     //!!!!!
            ans>=mo?ans-=mo:0;
        }
    }
    printf("%lld\n",ans);
    return 0;
}