格雷码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef unsigned long long ull;

ull n,k;

int main(void){
    scanf("%llu%llu",&n,&k);
    k^=(k>>1);
    for(reg ull i=n;i>=1;--i)
        if(k&(1ull<<(i-1)))
            putchar('1');
        else
            putchar('0');
    putchar('\n');
    return 0;
}

括号树

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXN=500000+5;

int n;
char val[MAXN];
int fa[MAXN];
int cnt,head[MAXN],to[MAXN],Next[MAXN];
ll f[MAXN];
ll sum[MAXN];
int top;
int S[MAXN];

inline void Add_Edge(reg int,reg int);
inline void DFS(reg int);

int main(void){
    scanf("%d\n%s",&n,val+1);
    for(reg int i=2;i<=n;++i){
        scanf("%d",&fa[i]);
        Add_Edge(fa[i],i);
    }
    DFS(1);
    reg ll ans=0;
    for(reg int i=1;i<=n;++i)
        ans^=(ll)i*sum[i];
    printf("%lld\n",ans);
    return 0;
}

inline void Add_Edge(reg int u,reg int v){
    Next[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    return;
}

inline void DFS(reg int ID){
    int flag=0;
    if(val[ID]=='(')
        S[++top]=ID;
    else
        if(top){
            flag=S[top];
            f[ID]=f[fa[flag]]+1;
            --top;
        }
    sum[ID]=sum[fa[ID]]+f[ID];
    for(reg int i=head[ID];i;i=Next[i])
        DFS(to[i]);
    if(flag)
        S[++top]=flag;
    else if(top)
        --top;
    return;
}

Emiya 家今天的饭

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 998244353ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg ll res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100+5;
const int MAXM=2000+5;

int n,m;
ll a[MAXN][MAXM];
ll sum[MAXN];
ll dp[MAXN][MAXN<<1];

int main(void){
    reg ll ans=1;
    n=read(),m=read();
    for(reg int i=1;i<=n;++i)
        for(reg int j=1;j<=m;++j)
            a[i][j]=read(),sum[i]=(sum[i]+a[i][j])%MOD;
    for(reg int i=1;i<=n;++i)
        ans=ans*((sum[i]+1)%MOD)%MOD;
    --ans;
    for(reg int i=1;i<=m;++i){
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(reg int j=1;j<=n;++j)
            for(reg int k=0;k<=(n<<1);++k){
                dp[j][k]=(dp[j][k]+dp[j-1][k]*((sum[j]-a[j][i]+MOD)%MOD)%MOD)%MOD;
                dp[j][k+1]=(dp[j][k+1]+dp[j-1][k])%MOD;
                dp[j][k+2]=(dp[j][k+2]+dp[j-1][k]*a[j][i]%MOD)%MOD;
            }
        for(reg int j=n+1;j<=(n<<1);++j)
            ans=(ans+MOD-dp[n][j])%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}

划分

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=40000000+5;
const int MAXM=100000+5;
const int MAXSIZE=11;
const int BASE=10000;
const int LGBASE=4;

struct BigNumber{
    int len;
    int unit[MAXSIZE];
    inline BigNumber(void){
        len=1;
        memset(unit,0,sizeof(unit));
        return;
    }
    inline BigNumber(reg ll a){
        reg int i;
        for(i=0;a!=0&&i<MAXSIZE;++i){
            unit[i]=a%BASE;
            a/=BASE;
        }
        len=i-1;
        return;
    }
    inline void Fresh(void){
        reg int i;
        for(i=0;i<MAXSIZE-1;++i)
            if(unit[i]>=BASE){
                unit[i+1]+=unit[i]/BASE;
                unit[i]%=BASE;
            }
        for(i=MAXSIZE-1;i>=0;--i)
            if(unit[i]){
                len=i;
                break;
            }
        if(i==-1)
            len=1;
        return;
    }
    inline void Add(const BigNumber& a){
        for(reg int i=0,l=max(len,a.len);i<=l;++i)
            unit[i]+=a.unit[i];
        Fresh();
        return;
    }
    inline void Mul(const BigNumber& a){
        BigNumber res;
        for(reg int i=0;i<=len;++i)
            for(reg int j=0;j<=a.len;++j)
                res.unit[i+j]+=unit[i]*a.unit[j];
        *this=res;
        Fresh();
        return;
    }
    inline void Opt(reg ll a){
        BigNumber temp(a);
        temp.Mul(temp);
        this->Add(temp);
        return;
    }
    inline void Print(void){
        printf("%d",unit[len]);
        for(reg int i=len-1;i>=0;--i)
            printf("%0*d",LGBASE,unit[i]);
        putchar('\n');
        return;
    }
};

int n,type;
int x,y,z,m;
int a[MAXN],b[MAXN];
int p[MAXM],l[MAXM],r[MAXM];
ll sum[MAXN];
BigNumber ans;
int pre[MAXN];
int head,tail,Q[MAXN];

inline ll Calc(reg int);

int main(void){
    n=read(),type=read();
    if(type==0)
        for(reg int i=1;i<=n;++i)
            a[i]=read();
    else{
        x=read(),y=read(),z=read(),b[1]=read(),b[2]=read(),m=read();
        for(reg int i=1;i<=m;++i)
            p[i]=read(),l[i]=read(),r[i]=read();
        for(reg int i=1;i<=m;++i){
            for(reg int j=p[i-1]+1;j<=p[i];++j){
                if(j>=3)
                    b[j]=((ll)x*b[j-1]+(ll)y*b[j-2]+z)%(1<<30);
                a[j]=b[j]%(r[i]-l[i]+1)+l[i];
            }
        }
    }
    for(reg int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i];
    head=tail=1;
    for(reg int i=1;i<=n;++i){
        while(head<tail&&Calc(Q[head+1])<=sum[i])
            ++head;
        pre[i]=Q[head];
        while(head<tail&&Calc(Q[tail])>=Calc(i))
            --tail;
        Q[++tail]=i;
    }
    reg int now=n;
    while(now){
        ans.Opt(sum[now]-sum[pre[now]]);
        now=pre[now];
    }
    ans.Print();
    return 0;
}

inline ll Calc(reg int x){
    return (sum[x]<<1)-sum[pre[x]];
}