【Codeforces 868 G】— El Toll Caves（类欧几里得）

考虑从左往右每次填 $k$ 个
设 $E[i]$ 表示如果宝藏在 $i$ 的期望步数
有 $E[i+k]=E[i]+1(i<=n-k)$
$E[i+k-n]=p+(1-p)(E[i]+1)(otherwise)$
这样可以手动消元 $O(n)$ 做

实际上要求的是 $sum E[1...n]$
考虑可以把 $\%k$ 相同的归到一类
然后就发现只需要求 $E[1...k]$ 就可以了
每个 $E[i]$ 有个系数
相当于是 $x->ax+b$ 这样的函数
发现前 $n\%k$ 个和剩下的系数不一样
分别把2种函数设成 $f1,f2$

考虑每次的 $f1,f2$ 的变化和 $E$ 的两种关系式有关
设为 $A,B$ ，即 $E[i+k]=A(E[i]),E[i+k-n]=B(E[i])$
发现每次 $f1,f2$ 变化为
$f1<-f1+sum_{i=1}^{n/k}f2(A^i)$
$f2<-f1+sum_{i=1}^{n/k-1}f2(A^i)$
于是考虑维护 $A,B$
以 $A$ 为例,考虑 $A$ 的意义，
即需要找到 $A'$ 使 $E[i+n\%k]=A'(E[i])$
把下标变换算一下可以得到 $A'=A^{-n/k+1}(B^{-1})$
$B'$ 类似算一下就可以了

~~题解写的很口胡请见谅~~

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>  
cs int mod=1e9+7;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?a+=mod:0;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline void Mul(int &a,int b){a=1ll*a*b%mod;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
struct node{
	int x,y;
	node(int _x=0,int _y=0):x(_x),y(_y){}
	friend inline node operator +(cs node &a,cs node &b){
		return node(add(a.x,b.x),add(a.y,b.y));
	}
	friend inline node operator +(cs node &a,cs int &b){
		return node(a.x,add(a.y,b));
	}
	friend inline node operator -(cs node &a,cs node &b){
		return node(dec(a.x,b.x),dec(a.y,b.y));
	}
	friend inline node operator -(cs node &a,cs int &b){
		return node(a.x,dec(a.y,b));
	}
	friend inline node operator *(cs node &a,cs node &b){
		return node(mul(a.x,b.x),add(mul(a.y,b.x),b.y));
	}
	int calc(int a){
		return add(mul(a,x),y);
	}
};
inline node Inv(node x){
	int t=Inv(x.x);
	x.x=t,x.y=dec(0,mul(x.y,t));
	return x;
}
inline node ksm(node a,int b){
	node res(1,0);
	for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
	return res;
}
inline int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
inline node S(node a,int b){
	if(!b)return node(0,0);
	if(a.x==1)return node(b,1ll*b*(b+1)/2%mod*a.y%mod);
	node x=ksm(a,b+1)-a,p;
	p.x=mul(x.x,Inv(a.x-1));
	p.y=mul(mul(dec(p.x,b),Inv(dec(a.x,1))),a.y);
	return p;
}
inline int solve(int n,int k,node A,node B,node f1,node f2){
	if(k==0){return f2.calc(mul(dec(0,A.y),Inv(dec(A.x,1))));}
	int k1=n%k,t=n/k;
	node F1=f1+S(A,t)*f2;
	node F2=f1+S(A,t-1)*f2;
	node a=Inv(B)*ksm(Inv(A),t-1),b=Inv(B)*ksm(Inv(A),t);
	return add(solve(k,k1,a,b,node(F1.x,0),node(F2.x,0)),add(mul(k1,F1.y),mul(k-k1,F2.y)));
}
int n,k,p;
node f1,f2,A,B;
int main(){
	int T=read();
	while(T--){
		n=read(),k=read(),p=Inv(2);
		int g=gcd(n,k);n/=g,k/=g;
		f1=node(1,0),f2=node(1,0),A=node(1,1),B=node(dec(1,p),1);
		cout<<mul(solve(n,k,A,B,f1,f2),Inv(n))<<'
';
	}
}

【Codeforces 868 G】— El Toll Caves（类欧几里得）

相关推荐