难度:省选+

毒瘤比赛。

Problem A: 整数

题意:

题解:

我就是这题终于弄懂了生成函数。

NTT原理也太优秀了。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 150005
#define Mod 786433
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
il ll qpw(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return res;
}
ll fac[Mod+5],ifac[Mod+5],inv[Mod+5],gpw[Mod+2];
il void init()
{
    gpw[0]=fac[0]=ifac[0]=1;
    for(int i=1;i<=Mod-1;i++)
        fac[i]=fac[i-1]*i%Mod,inv[i]=qpw(i,Mod-2),gpw[i]=gpw[i-1]*10%Mod;
    ifac[Mod-1]=qpw(fac[Mod-1],Mod-2);
    for(int i=Mod-2;i>=1;i--)
        ifac[i]=ifac[i+1]*(i+1)%Mod;
    //cout<<inv[1]<<endl;
}
namespace ntt
{
    ll w1[Max],w2[Max];
    int r[Max],n=131072;
    il void init()
    {
        for(int i=1;i<=n;i<<=1)
        {
            w1[i]=qpw(10,(Mod-1)/i);
            w2[i]=inv[w1[i]];
        }
        r[0]=0;
        for(int i=1;i<n;i++)
            r[i]=((r[i>>1]>>1)|((i&1)?n>>1:0));
    }
    il void NTT(ll *A,int idft)
    {
        for(int i=1;i<n;i++)
            if(r[i]<i) swap(A[i],A[r[i]]);
        for(int mid=1;mid<n;mid<<=1)
        {
            ll len=mid<<1,wn=(idft==1)?w1[len]:w2[len];
            for(int i=0;i<n;i+=len)
            {
                ll w=1;
                for(int j=0;j<mid;j++,w=w*wn%Mod)
                {
                    ll x=A[i+j],y=w*A[i+mid+j]%Mod;
                    A[i+j]=(x+y);
                    A[i+mid+j]=(x-y+Mod);
                    if(A[i+j]>=Mod) A[i+j]-=Mod;
                    if(A[i+mid+j]>=Mod) A[i+mid+j]-=Mod;
                }
            }
        }
        if(idft==-1)
        {
            for(int i=0;i<n;i++) A[i]=A[i]*inv[n]%Mod*fac[i]%Mod;
        }
    }
}
int lim=131072;
int n,m,k,c[15][Max];
ll ans,f[Max],f2[Max],a[Max],d[15][Max];
char s[Max];
int main()
{
    init();
    ntt::init();
    k=read(),n=read(),m=read();
    for(int i=1;i<k;i++)
    {
        scanf("%s",s);
        for(int j=0;j<=n;j++)
            c[i][j]=s[j]-'0';
    }
    for(int i=0;i<lim;i++) f[i]=1;
    for(int i=1;i<=k-1;i++)
    {
        ll *u=d[i];
        for(int j=0;j<lim;j++)
            u[j]=0;
        for(int j=0;j<=n;j++)
            u[j]=c[i][j]*ifac[j]%Mod;
        ntt::NTT(u,1);
        //for(int j=0;j<=n;j++) cout<<u[j]<<"qwqqwqqqwq\n";
        for(int j=0;j<lim;j++)
        {
            if(u[j]) f[j]=f[j]*u[j]%Mod;//,puts("qwqwq");
            else f2[j]++;//,puts("qwqwq");
        }
    }
    for(int i=0;i<lim;i++)
        if(!f2[i]) a[i]=f[i];//,cout<<i<<' '<<f[i]<<" qwq!\n";
    while(m--)
    {
        int x=read(),y=read();
        c[x][y]^=1;
        for(int i=0;i<lim;i++)
        {
            if(d[x][i]) f[i]=f[i]*inv[d[x][i]]%Mod;
            else f2[i]--;
        }
        ll s1=gpw[((Mod-1)/lim*y)%(Mod-1)],s2=ifac[y];
        //cout<<s1<<' '<<s2<<" qwqwq\n";
        if(!c[x][y]) s2=Mod-s2;
        for(int i=0;i<lim;i++)
        {
            d[x][i]+=s2;
            if(d[x][i]>=Mod) d[x][i]-=Mod;
            s2=s2*s1%Mod;
        }
        for(int i=0;i<lim;i++)
        {
            if(d[x][i]) f[i]=f[i]*d[x][i]%Mod;
            else f2[i]++;
            if(!f2[i]) a[i]=(a[i]+f[i])%Mod;
        }
    }
    ntt::NTT(a,-1);
    for(int i=1;i<lim;i++) ans=(ans+a[i])%Mod;
    cout<<ans<<endl;
}

Problem B: 2048

题意:

题解:

挺毒瘤的,最坏复杂度没保证,但是好像卡不掉。

跑一个dfs,维护一个从左到右递增再递减的数列,然后发现可以用类似状压的思想,拿一个int维护一下合并情况,中间保证左边的最大值大于右边的就好了。

中间是自动合并的所以码量不是很大。

维护一个前缀和,你知道左边的和就知道右边的和了,所以只要维护左边的递增数列和就好了。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define int long long
#define Max 100005
#define dg puts("qwqwqwqwq")
using namespace std;
il ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,a[Max],flg,l,r,ans[Max],hb[Max],s[Max],sm,vst[1005][9005],T,tot;
il void print()
{
    for(int i=1;i<=n;i++)
        if(ans[i]) putchar('r');
        else putchar('l');
    puts("");
}
il int lb(int x)
{
    return x&-x;
}
il void dfs(int x,int ls)
{
    //cout<<x<<' '<<s[x]<<endl;
    if(hb[s[x]-ls]>=hb[ls]) ls+=hb[s[x]-ls];
    //cout<<x<<' '<<ls<<endl;
    if(vst[x][ls]==tot) return;
    //dg;
    vst[x][ls]=tot;
    if(x==n)
    {
        if(ls==s[n]&&ls==lb(ls)) flg=1,print();
        return;
    }
    if(a[x+1]<=lb(ls)) ans[x+1]=0,dfs(x+1,ls+a[x+1]);
    if(flg) return;
    if(!lb(s[x]-ls)||a[x+1]<=lb(s[x]-ls)) ans[x+1]=1,dfs(x+1,ls);
}
il void init()
{
    for(int i=2;i<=10000;i++) hb[i]=hb[i>>1]+1;
    for(int i=1;i<=10000;i++) hb[i]=1<<hb[i];
}
signed main()
{
    init();
    T=read();
    while(T--)
    {
        tot++;
        n=read();
        sm=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            s[i]=s[i-1]+a[i];
            sm+=a[i];
        }
        //cout<<sm<<" qwq\n";
        ans[1]=0;
        flg=0;
        dfs(1,a[1]);
        if(!flg) puts("no");
    }
}

Problem C: Subsequence Count

题意:

n,q \leq 10^5

题解:

挺神仙的一题。

dp就挺难想的,网上各种题解说的简单dp都是假的(可能是我太菜了

f[i][j]表示第i个字符以j结尾的本质不同子串数量。

那么有:

f[i][s[i]]=f[i-1][s[i]^1]+f[i-1][s[i]]+1

f[i][s[i]^1]=f[i-1][s[i]^1]

解释一下为什么是这样。

首先f[i][s[i]^1]因为不能加上当前的s[i]所以直接从上一个转移(如果加上了会有重复计数)。

f[i][s[i]]可以理解为先加上两个f[i-1][s[i]]在减去重复计数的部分f[i-1][s[i]]再加上1。

然后考虑怎么修改。

发现dp可以用两个矩阵表示转移:

s[i]==0:

1 0 0

1 1 0

1 0 1

s[i]==1:

1 1 0

0 1 0

0 1 1

博客里的katex插件好像有锅,所以矩阵弄不出来,就这样搞搞好了。

初始矩阵把第三行第一个和第二个数改成f[i][0]f[i][1]就行。

然后用线段树维护矩阵乘积。

考虑反转怎么弄。

还是类似线段树打标记,每次下传标记的时候交换矩阵第一,二行和第一,二列就好了。

为什么是对的呢?我已经想到了一个绝妙的证明,可惜这里位置太小写不下了。(咕咕咕

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 200005
#define Mod 1000000007
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct mat
{
    ll m[3][3];
}c,o,k[2],t[Max<<2],ans;
int tg[Max<<2];
char s[Max];
il mat operator * (mat x,mat y)
{
    mat z=o;
    for(int i=0;i<3;i++)
        for(int k=0;k<3;k++)
            for(int j=0;j<3;j++)
            {
                z.m[i][j]=(1ll*z.m[i][j]+1ll*x.m[i][k]*y.m[k][j])%Mod;
            }
    return z;
}
il void pushup(int x)
{
    t[x]=t[ls(x)]*t[rs(x)];
}
il void rev(int x)
{
    swap(t[x].m[0][0],t[x].m[0][1]);
    swap(t[x].m[1][0],t[x].m[1][1]);
    swap(t[x].m[2][0],t[x].m[2][1]);
    swap(t[x].m[0],t[x].m[1]);
}
il void pushdown(int x)
{
    if(tg[x])
    {
        tg[ls(x)]^=1;
        tg[rs(x)]^=1;
        tg[x]=0;
        rev(ls(x)),rev(rs(x));
    }
}
il void build(int x,int l,int r)
{
    if(l==r)
    {
        t[x]=k[s[l]-'0'];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    pushup(x);
}
il void mdf(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        rev(x);
        tg[x]^=1;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(x);
    if(ql<=mid) mdf(ls(x),l,mid,ql,qr);
    if(qr>mid) mdf(rs(x),mid+1,r,ql,qr);
    pushup(x);
}
il mat qry(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        return t[x];
    }
    int mid=(l+r)>>1;
    pushdown(x);
    mat res=c;
    if(ql<=mid) res=res*qry(ls(x),l,mid,ql,qr);
    if(qr>mid) res=res*qry(rs(x),mid+1,r,ql,qr);
    //pushup(x);
    return res;
}
int n,q;
il void write(int x)
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
il int md(int x)
{
    return x>=Mod?x-Mod:x;
}
signed main()
{
    //freopen("C.in","r",stdin);
    //freopen("C.out","w",stdout);
    for(int i=0;i<3;i++) c.m[i][i]=1;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            o.m[i][j]=0;
    k[0]=
    {
     1,0,0,
     1,1,0,
     1,0,1
    };
    k[1]=
    {
     1,1,0,
     0,1,0,
     0,1,1
    };
    n=read(),q=read();
    for(int i=1;i<=n;i++) s[i]=getchar();
    build(1,1,n);
    int opt,l,r;
    while(q--)
    {
        opt=read(),l=read(),r=read();
        if(opt==1) mdf(1,1,n,l,r);
        else
        {
            ans=qry(1,1,n,l,r);
            write(md(1ll*ans.m[2][0]+1ll*ans.m[2][1]));
            putchar('\n');
        }
    }
}