2023牛客暑假多校1

J

画出状态树发现有重合部分。

动手推推即可发现递推式。

但是这个递推式是 $O(n)$ 的。

容易发现，这个递推的值是一块一块分布的，所以可以一块一块地统计。

结合快速幂即可 $O(\log^2n)$ 解决本题。

代码

#include<bits/stdc++.h>
#define ll long long 

using namespace std;

const ll mod=998244353;

ll n,m;
map<int,ll> a;

ll qpow(ll x,ll y) {
    if(!y) return 1;
    ll t=qpow(x,y>>1);
    if(y&1) return t*t%mod*x%mod;
    else return t*t%mod;
}

void work() {
    cin>>n>>m;
    a[n+m]=1;
    for(int i=n+m-1;i>=n;i--) {
        ll t=(ll)log2(i+1);
        a[i]=a[i+1]*(((1-qpow(qpow(2,t),mod-2))%mod+mod)%mod)%mod;
    }    
    cout<<a[n]<<endl;
}

int main() {
    work();
    return 0;
}

---

M

容易想到裴蜀定理。

当 $gcd(A,B) \nmid x$ 时，输出 -1 。

假设一组解为 $(r_0,s_0)$ ，那么动手模拟可以发现操作次数要么是 $2(r_0+s_0)$ ，要么是 $2|r_0-s_0|-1$ 。

题解中的证明：

于是用扩欧求出距离原点较近的解，对附近的特解取 min 即可。

代码

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

ll x,y;
ll gcd(ll x,ll y) {
	return !y?x:gcd(y,x%y);
}
void Exgcd(ll a,ll b) {
	if(!b) x=1,y=0;
	else {
		Exgcd(b,a%b);
		int t=x;
		x=y,y=t-a/b*y;
	}
}

int T;

ll a,b,c;
void work() {
    scanf("%lld%lld%lld",&a,&b,&c);
    Exgcd(a,b);
    ll d=gcd(a,b);
    if(c%d!=0) printf("-1\n");
    else {
    	a/=d,b/=d,c/=d;
        x=x*c,y=y*c;
        x=(x%b+b)%b;
        y=(c-a*x)/b;
        ll ans=max(2*(x+y),2*abs(x-y)-1);
        for(int i=-10;i<=10;i++) {
        	ll xx,yy;
            xx=x+i*b;
            yy=y-i*a;
            ans=min(ans,max(2*(xx+yy),2*abs(xx-yy)-1));
        }
        printf("%lld\n",ans);
    }
}

int main() {
    scanf("%d",&T);
    while(T--) work();
    return 0;
}