2017.2.18模拟赛总结反思

第一次模拟赛被绍一大爷虐惨了。。。。

看T1 woc这不是SB虚树么？打上ST表之后发现自己丝薄了。。
听着别人键盘噼里啪啦蜜汁心慌

一小时后我才发现T1可以 O(n32) 的做然后感觉复杂度太高看着旁边Manchery已经码起来了感觉很害怕问了一下复杂度居然和我一样于是我也不虚了

然后调出大样例手造数据发现自己代码跑的还蛮快的

之后开始刚第三题突然Manchery说自己的树分块常数好大 ~~您这代码复杂度真的对么~~ 感觉药丸

然后Manchery全程喊着心态爆炸压常数无望之后找我~~嘿嘿嘿~~ 我跟他说了一个时间复杂度稳定的算法最后他顺利过了T1 我因为没有开longlong 答案爆了int 加上捆绑测试只有25分 ~~EXM?~~

T1打完接下来离结束还有2h
喜闻乐见的Go die时间能多拿一分是一分

结束
得知T1要开longlong的我眼泪掉下来，~~Dirak大爷造的数据真TM良心~~ MD只有25的暴力分
然后70分成功被虐惨
~~要是145分的话貌似已经是rk4了？~~

T1 任轩笛打野的 O(n32) 貌似成功草了标算?
~~我貌似更简单的算法成功把它和标算都草了一遍？~~

反思：
题目没想清楚不要动手
注意变量范围
不要慌

T1:
大约思想就是分类讨论感觉还是蛮好玩的一个题吧

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
using namespace std;
#define pb push_back
#define ll long long
char c;
inline void read(int&a)
{
    a=0;do c=getchar();while(c<'0'||c>'9');
while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}

struct Chain
{int u;Chain*next;}*Head[200001];

inline void Add(int u,int v)
{
    Chain*tp=new Chain;tp->next=Head[u];Head[u]=tp;tp->u=v;
}
int n,r,q;
int size[200001];
int Limi,co[200001];
bool BIG[200001];
vector<int> AsSon[200001],AsFa[200001];
struct L
{
int a,b;
const friend bool operator <(const L a,const L b){return a.a^b.a?a.a<b.a:a.b<b.b;}
}Q[200001];
int B[200001];
int Cnt[200001];
ll Ans[200001];
void Solve_update(int u)
{

    Cnt[co[u]]++;
for(int i=0;i<AsSon[co[u]].size();i++)
    {
int j=Q[AsSon[co[u]][i]].a;
        Ans[AsSon[co[u]][i]]+=Cnt[j];
    }
for(Chain*tp=Head[u];tp;tp=tp->next)
        Solve_update(tp->u);
    Cnt[co[u]]--;
}

void Solve_subtree(int u)
{
for(int i=0;i<AsFa[co[u]].size();i++)
    {
int j=Q[AsFa[co[u]][i]].b;
        Ans[AsFa[co[u]][i]]-=Cnt[j];
    }
    Cnt[co[u]]++;
for(Chain*tp=Head[u];tp;tp=tp->next)
        Solve_subtree(tp->u);
for(int i=0;i<AsFa[co[u]].size();i++)
    {
int j=Q[AsFa[co[u]][i]].b;
        Ans[AsFa[co[u]][i]]+=Cnt[j];
    }

}
int fa[200001];
int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]);}
#define mp make_pair
map<L ,int>Has;
int main()
{
    read(n),read(r),read(q);
    read(co[1]);
    size[co[1]]++;
for(int i=2;i<=n;i++)
    {
int k;read(k);
        Add(k,i);
        read(co[i]);
        size[co[i]]++;
    }
    Limi=sqrt(n);
for(int i=1;i<=r;i++)
if(size[i]>Limi)BIG[i]=true,B[++B[0]]=i;
    Has.clear();
for(int i=1;i<=q;i++)
    {
        read(Q[i].a),read(Q[i].b);
int &T=Has[Q[i]];
if(T)fa[i]=T;
else
        {
            fa[i]=T=i;
if(!BIG[Q[i].b])AsSon[Q[i].b].pb(i);
if(BIG[Q[i].b])AsFa[Q[i].a].pb(i);
        }
    }
    Solve_update(1);
    Solve_subtree(1);
for(int i=1;i<=q;i++)printf("%lld\n",Ans[F(i)]);
return 0;
}

T2
吓傻
瞎作只搞出来入度小于2 但完全不知道怎么搞啊。。
Orx题解的拆圈并圈

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
const
int Mod=998244353;
using namespace std;
int deg[100001],a[100001],num[100001],l[100001],d[100001];
bool vis[100001];
int Fact[100001],Inv[100001];
inline int Pow(int a,int x)
{
int res=1;
for(;x;x>>=1,a=a*1ll*a%Mod)
if(x&1)res=a*1ll*res%Mod;
return res;
}
queue<int>Q;
inline int C(int x,int y){return Fact[x]*1ll*Inv[y]%Mod*Inv[x-y]%Mod;}
#define x first
#define y second
#define mp make_pair
#define pb push_back

vector<pair<int,int> >Cir;

inline int pr(int n)
{
return Fact[n<<1]*1ll*Inv[n]%Mod*Pow(Mod+1>>1,n)%Mod;
}
int main()
{
    Fact[0]=1;
for(int i=1;i<=100000;i++)Fact[i]=Fact[i-1]*1ll*i%Mod;
    Inv[100000]=Pow(Fact[100000],Mod-2);
for(int i=99999;~i;i--)Inv[i]=Inv[i+1]*(i+1ll)%Mod;    
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i),deg[a[i]]++;
for(int i=1;i<=n;i++)if(deg[i]>2)return puts("0"),0;
for(int i=1;i<=n;i++)if(!(d[i]=deg[i]))Q.push(i);
while(!Q.empty())
    {
int u=Q.front();Q.pop();
        vis[u]=1;
if(!--d[a[u]])Q.push(a[u]);
    }
for(int i=1;i<=n;i++)if(vis[i]&&deg[i]>1)return puts("0"),0;
for(int i=1;i<=n;i++)if(vis[i]&&!deg[i])
    {
int x=i,cnt=0;
for(;vis[x];x=a[x])cnt++;
        l[x]=cnt;
    }
int ans=1;
for(int i=1;i<=n;i++)if(!vis[i])
    {
int x=i,fl=0,tp=1,tot=0;
for(;!vis[x];x=a[x])++tot,fl|=l[x],vis[x]=1;
if(!fl){num[tot]++;continue;}
        Cir.clear();
int p=1;x=i;
do
        {
if(l[x])Cir.pb(mp(l[x],p));
            x=a[x];p++;
        }while(x^i);
        Cir.pb(mp(Cir[0].x,Cir[0].y+tot));
for(int j=1;j<Cir.size();j++)
if(Cir[j].x>Cir[j].y-Cir[j-1].y)tp=0;
else if(Cir[j].x^(Cir[j].y-Cir[j-1].y))tp=tp*2ll%Mod;
        ans=ans*1ll*tp%Mod;
    }

for(int i=1;i<=n;i++)if(num[i])
    {
int m=num[i],tp=0;
for(int j=0;j<=m/2;j++)
            {
int tp2=1ll*C(m,2*j)*pr(j)%Mod*Pow(i,j)%Mod;
if(i>1&&(i&1))tp2=tp2*1ll*Pow(2,m-2*j)%Mod;
                tp=(tp+tp2)%Mod;
            }
        ans=ans*1ll*tp%Mod;
    }
printf("%d\n",ans);
return 0;
}

T3
具体就是构造生成函数然后FFT加速递推。。
感觉自己啥都不会啊居然不知道FFT构造生成函数还能这样用涨姿势

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
using namespace std;

char S[1000002];
int l;
int pre[2000001];
int C[2000001];
const
int Mod=998244353,p=3;
inline void Up(int &a,int x)
{
    a+=x;
if(a>=Mod)a-=Mod;
else if(a<0)a+=Mod;
}

inline int Mul(int a,int b){return a*1ll*b%Mod;}
inline int Add(int a,int b)
{
    a+=b;
if(a>=Mod)a-=Mod;
else if(a<0)a+=Mod;
return a;
}
inline int Pow(int a,int x)
{
int res=1;
for(;x;x>>=1,a=a*1ll*a%Mod)
if(x&1)res=res*1ll*a%Mod;
return res;
}
int Rev[2000001];
inline void FFT(int*A,int N,int fl)
{
for(int i=0;i<(1<<N);i++)Rev[i]=Rev[i>>1]>>1|((1&i)<<N-1);
for(int i=0;i<(1<<N);i++)
if(Rev[i]>i)swap(A[i],A[Rev[i]]);
for(int i=1;i<(1<<N);i*=2)
    {
int W0=Pow(p,fl==1?(Mod-1)/2/i:(Mod-1-(Mod-1)/2/i));
for(int j=0;j<(1<<N);j+=i<<1)
        {
int W=1;
for(int k=0;k<i;k++)
            {
int X=A[j+k],Y=Mul(W,A[i+j+k]);
                A[j+k]=Add(X,Y);
                A[i+j+k]=Add(X,-Y);
                W=Mul(W,W0);
            }
        }
    }
if(fl==-1)
    {
int I=Pow(1<<N,Mod-2);
for(int i=0;i<(1<<N);i++)A[i]=Mul(A[i],I);
    }
}

int G[2000001],P[2000001],inv[2000001];
void Inv(int N)
{
if(N==0){inv[0]=1;return ;}
    Inv(N-1);
int Len=1<<N+1;
for(int i=0;i<(1<<N);i++)
        G[i]=C[i];
for(int i=(1<<N);i<Len;i++)G[i]=0;
    FFT(G,N+1,1);
    FFT(inv,N+1,1);
for(int i=0;i<Len;i++)inv[i]=Add(Mul(inv[i],2),-Mul(inv[i],Mul(inv[i],G[i])));
    FFT(inv,N+1,-1);
for(int i=1<<N;i<Len;i++)inv[i]=0;
}


int A[2000001];
int FK[2000001];

void Mul(int*a,int *b,int N)
{
    FFT(a,N+1,1);
if(a!=b)FFT(b,N+1,1);
for(int i=0;i<(1<<N+1);i++)a[i]=Mul(a[i],b[i]);
    FFT(a,N+1,-1);
if(a!=b)FFT(b,N+1,-1);
for(int i=1<<N;i<(1<<N+1);i++)a[i]=0;
}

void MPow(int *F,int x,int N)
{
//FK[0]=1;
for(int i=0;i<1<<N;i++)
        FK[i]=G[i];
for(;x;x>>=1)
    {
if(x&1)
            {Mul(FK,F,N);}
        Mul(F,F,N);
    }
}
int main()
{
scanf("%s",S+1);
    l=strlen(S+1);
int k,n;
scanf("%d%d",&n,&k);
    pre[0]=-1;
for(int i=1;i<=l;i++)
    {
int j=pre[i-1];
while(~j&&S[j+1]!=S[i])j=pre[j];
        pre[i]=j+1;
    }
int t=pre[l];
for(;t;)C[l-t]++,t=pre[t];

int N=1;
while((1<<N)<=max(n,l))N++;
    N++;

for(int i=l,t=1;i<(1<<N);t=t*26ll%Mod,i++)Up(C[i],t);
    C[0]=1;
    Inv(N);
    FFT(inv,N+1,1);

    A[l]=1;
for(int i=l+1;i<(1<<N);i++)A[i]=Mul(A[i-1],26);
    FFT(A,N+1,1);
for(int i=0;i<(1<<N+1);i++)inv[i]=Mul(inv[i],A[i]);
    FFT(inv,N+1,-1);
for(int i=0;i<1<<N;i++)inv[i]=inv[i+l];
for(int i=1<<N;i<(1<<N+1);i++)inv[i]=0;
for(int i=l;i<(1<<N);i++)P[i]=inv[i-l];
    A[0]=1;
for(int i=1;i<(1<<N);i++)A[i]=Mul(A[i-1],26);
for(int i=1<<N;i<(1<<N+1);i++)A[i]=0,P[i]=0;
    FFT(P,N+1,1);
    FFT(A,N+1,1);
for(int i=0;i<(1<<N+1);i++)G[i]=Mul(A[i],P[i]);
    FFT(G,N+1,-1);


//return 0;
int Ans=0;

    N=1;
while((1<<N)<=n)N++;
    N++;

for(int K=1,i=0;i<1<<N;i++,K=Mul(K,26))G[i]=Add(K,-G[i]);
for(int i=1<<N;i<(1<<N+1);i++)G[i]=0;
for(int i=1<<N;i<(1<<N+1);i++)inv[i]=0;
    MPow(inv,k,N);
for(int i=0;i<=n;i++)
        Up(Ans,FK[i]);
cout<<Ans<<endl;

return 0;
}

秒客网

2017.2.18模拟赛总结反思

相关文章