[题解] Atcoder Beginner Contest ABC 270 G Ex 题解

点我看题

G - Sequence in mod P

稍微观察一下就会发现，进行x次操作后的结果是\(A^xS+(1+\cdots +A^{x-1})B\)。如果没有右边那一坨关于B的东西，那我们要求的就是满足\(A^x \equiv \frac GS\)的最小的x(离散对数)。有一个叫BSGS的东西是专门干这个的

考虑能不能把这个式子直接化成\(A^x \equiv B\)的形式。先把答案=0、A=0和A=1的情况特判掉，因为会影响后面推式子。

\[\begin{align}
A^xS+(1+\cdots+A^{x-1})B&\equiv G\\
A^xS+\frac{A^x-1}{A-1}B&\equiv G(等比数列求和)\\
A^xS+\frac{A^x}{A-1}B&\equiv G+\frac1{A-1}B\\
A^x\cdot(S+\frac B{A-1})&\equiv G+\frac1{A-1}B\\
A^x&\equiv \frac{G+\frac B{A-1}}{S+\frac B{A-1}}
\end{align}
\]

进行上面的最后一步之前判断\(S+\frac B{A-1}\)是否为0，如果是0的话答案就是1，因为之前已经特判过答案为0的情况了；否则就直接跑BSGS就行了。

边界很多，写的时候注意一点。

时间复杂度\(O(t\sqrt P)\)。

点击查看代码

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)

#define repn(i,n) for(int i=1;i<=n;++i)

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

#define MOD P

using namespace std;

LL t,P,A,B,S,G,lim;

map <LL,LL> mp;

LL qpow(LL x,LL a)

{

	LL res=x,ret=1;

	while(a>0)

	{

		if((a&1)==1) ret=ret*res%MOD;

		a>>=1;

		res=res*res%MOD;

	}

	return ret;

}

int main()

{

  cin>>t;

  rep(tn,t)

  {

    cin>>P>>A>>B>>S>>G;

    if(S==G)

    {

      puts("0");

      continue;

    }

    if(A==0)

    {

      if(B==G) puts("1");

      else puts("-1");

      continue;

    }

    if(A==1)

    {

      if(B==0)

      {

        puts("-1");

        continue;

      }

      LL tmp=(G-S+P)%P;(tmp*=qpow(B,P-2))%=P;

      cout<<tmp<<endl;

      continue;

    }

    LL right=(G+B*qpow(A-1,P-2))%P,mul=(S+B*qpow(A-1,P-2))%P;

    if(mul==0)

    {

      if(right==0)

      {

        puts("1");

        continue;

      }

      puts("-1");

      continue;

    }

    (right*=qpow(mul,P-2))%=P;

    //A^ans = right

    //bsgs

    lim=ceil(sqrt((double)P));

    mp.clear();

    LL cur=1;

    rep(i,lim)

    {

      LL res=right*cur%P;

      if(mp.find(res)==mp.end()) mp[res]=i;

      else mp[res]=max(mp[res],(LL)i);

      (cur*=A)%=P;

    }

    LL bas=1;rep(i,lim) (bas*=A)%=MOD;

    cur=bas;

    LL ans=1e18;

    repn(a,lim)

    {

      if(mp.find(cur)!=mp.end())

      {

        LL curres=(LL)a*lim-mp[cur];

        if(curres<0) curres+=P-1;

        curres%=(P-1);

        ans=min(ans,curres);

      }

      (cur*=bas)%=P;

    }

    if(ans==1e18) puts("-1");

    else cout<<ans<<endl;

  }

	return 0;

}

Ex - add 1

官方题解精简版，供懒人食用。

注意到输入的a数组是单调不降的。令当前所有counter的值分别为\(c_1,c_2 \cdots c_n\)(下标从1开始)。定义一个\(c_1 \cdots c_n\)的状态的"值"为\(max_{i=1}^n\{max(0,a_i-c_i)\}\)。容易发现：这个值在\([0,a_n]\)中，值为0的时候我们就达到目标了，并且一次操作只能让这个值最多减少1。考虑一个值为k的状态(k>0)经过恰好1次操作会怎么变化。首先由于\(a_1=0,a_n>0\)，所以我们肯定可以找到唯一的r，满足\(a_r<k\leq a_{r+1}\)。现在开始进行操作，我们随机选择一个i把\(c_i\)归零。有两种情况：

\(i \leq r\)。\(a_i<k\)，所以任意一个\(c_i\)被归零都不会导致状态的新值达到或超过k。所以状态的值减一。
\(i>r\)。很显然状态的值会变成\(a_i\)。

所以可以发现所有值相等的状态都是"等价"的，至少它们达到目标的期望步数一定是相等的。令\(dp_i\)表示值为i的状态达到目标的期望步数。\(dp_0\)=0,我们要求\(dp_{a_n}\)。转移比较显然，是这样的：

\[\begin{align}
dp_i&=\frac 1n(r_i \cdot dp_{i-1}+\sum_{j=r_i+1}^n dp_{a_j})+1\\
dp_{i-1}&=\frac 1{r_i} (n(dp_i-1)-\sum_{j=r_i+1}^n dp_{a_j})
\end{align}
\]

其中\(r_i\)就是上面说的每个状态值对应的r。

其实这样已经可做了，但是毕竟我们要求的是\(dp_{a_n}\)，但这个式子是从后往前转移的，但我们要求\(dp_{a_n}\)，不太方便，所以可以转化一下：令\(f_i=dp_{a_n}-dp_i\)，把\(dp_i=dp_{a_n}-f_i\)带入上面的式子，并再把式子两边同时用\(dp_{a_n}\)减。

\[\begin{align}
dp_{a_n}-dp_{i-1}&=dp_{a_n}-\frac 1{r_i}(n \cdot (dp_{a_n}-f_i-1)-dp_{a_n}\cdot(n-r_i)+\sum_{j=r_i+1}^nf_{a_j}) \ \ \ \ \ \ 右边的dp_{a_n}都消掉了\\
f_{i-1} &= \frac 1{r_i}(n \cdot(f_i+1)-\sum_{j=r_i+1}^nf_{a_j})
\end{align}
\]

发现可以把\([0,a_n]\)这个区间分成n-1段处理，分别是\([a_0,a_1-1],[a_1,a_2-1]\cdots\)每段内部的dp转移都相同(因为\(r_{i+1}\)相同)。所以对每一段分别矩阵快速幂转移就可以了。官方题解还有复杂度更低一点的优化，但是这样已经可以过了，稍微有一点点卡常而已。

时间复杂度\(O(2^3\cdot nlog值域)\)。

点击查看代码

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)

#define repn(i,n) for(int i=1;i<=n;++i)

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)

{

	LL res=x,ret=1;

	while(a>0)

	{

		if((a&1)==1) ret=ret*res%MOD;

		a>>=1;

		res=res*res%MOD;

	}

	return ret;

}

LL n,a[200010],y[200010];

vector <vector <LL> > pw[70];

vector <vector <LL> > mul(vector <vector <LL> > a,vector <vector <LL> > b)

{

  vector <vector <LL> > ret={{0,0},{0,0}};

  rep(i,2) rep(j,2) rep(k,2) (ret[i][j]+=a[i][k]*b[k][j])%=MOD;

  return ret;

}

int main()

{

  cin>>n;

  repn(i,n) scanf("%lld",&a[i]);

  y[n]=0;

  LL sum=0;

  for(int i=n-1;i>0;--i)

  {

    if(a[i]==a[i+1])

    {

      y[i]=y[i+1];

      (sum+=y[i])%=MOD;

      continue;

    }

    LL r=i,add=(n*qpow(r,MOD-2)+(MOD-sum*qpow(r,MOD-2)%MOD))%MOD;

    pw[0]={{n*qpow(r,MOD-2)%MOD,1},{0,1}};

    vector <vector <LL> > res(0);

    LL dist=a[i+1]-a[i],cc=0;

    while(dist>0)

    {

      if(dist&1)

      {

        if(res.empty()) res=pw[cc];

        else res=mul(res,pw[cc]);

      }

      dist>>=1;++cc;

      if(dist==0) break;

      pw[cc]=mul(pw[cc-1],pw[cc-1]);

    }

    y[i]=(res[0][0]*y[i+1]+res[0][1]*add)%MOD;

    (sum+=y[i])%=MOD;

  }

  cout<<y[1]<<endl;

	return 0;

}

[题解] Atcoder Beginner Contest ABC 270 G Ex 题解

G - Sequence in mod P

Ex - add 1