AtCoder ARC #126 : F - Affine Sort

本番ではないけど、書いたコードが一発で通って意外だった。
https://atcoder.jp/contests/arc126/tasks/arc126_f

問題

N要素の整数列Xが与えられる。
整数(a,b,c)に対し、以下を満たす組み合わせの個数をf(K)とする。

• 1≦c≦K
• 0≦a＜c、0≦b＜c
• Y[i]=(aX[i]+b )%cとするとき、Y[i]が昇順である

Kを限りなく大きくしたとき、f(K)/(K^3)の極限値を求めよ。

解法

まずcのことを考えずに済むよう、g(c)をcを定めたときのa,bの組み合わせとする。
すると、f(K) = sum(g(i))であり、f(K)はg(K)/K^2の極限の1/3となる。
よって以降g(K)を考える。

Y[i]=(aX[i]+b)%Kなので、全体をKで割るとY[i]/Kは(aX[i]+b)/Kの小数部分となる。
α=a/K、β=b/Kとすると、結局αX[i]+βの整数部分が昇順であればよいことになる。

まずβは無視して、αX[i]の小数部分が昇順になることを考えよう。
αX[0]とαX[N-1]の値から、αX[0]～αX[N-1]が昇順となるようなβの範囲を求めることができる。
また、条件を満たすαは区間であり、βはαの関数である。

そこで、βをαの多項式として表現し、αに対し積分することで、条件を満たすα及びβの範囲を求めよう。
αについては、αX[0]～αX[N-1]の途中でそこを境界として順番が入れ替わるようなαがいくつかあるので、それらの値で区切られた区間毎に、αX[0]～αX[N-1]が昇順となるか判定しよう。

int N;
int X[1010];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

bool comp(pair<ll,ll> A,pair<ll,ll> B) {
	return A.first*B.second<A.second*B.first;
}

int ok(ll p,ll q) {
	ll a[1010];
	int i;
	FOR(i,N+1) {
		a[i]=(X[i]*p)%q;
	}
	ll ret=0;
	FOR(i,N) {
		if(a[i]==a[i+1]) return 0;
		if(a[i]<a[i+1]) ret+=a[i+1]-a[i];
		else ret+=q+a[i+1]-a[i];
	}
	return ret==q;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	X[N]=X[0];
	vector<pair<ll,ll>> C;
	C.push_back({0,1});
	C.push_back({1,1});
	FOR(i,N) {
		x=abs(X[i]-X[i+1]);
		for(j=1;j<x;j++) {
			k=__gcd(j,x);
			C.push_back({j/k,x/k});
		}
	}
	sort(ALL(C),comp);
	C.erase(unique(ALL(C)),C.end());
	ll ret=0;
	FOR(i,C.size()-1) {
		ll p=C[i].first*C[i+1].second+C[i].second*C[i+1].first;
		ll q=C[i].second*C[i+1].second*2;
		if(ok(p,q)) {
			ll L=C[i].first*modpow(C[i].second)%mo;
			ll R=C[i+1].first*modpow(C[i+1].second)%mo;
			if(X[N-1]>X[0]) {
				ll e=X[N-1]*p-X[0]*p;
				ll f=e/q+1;
				ret+=f*(R-L);
				ret+=-(X[N-1]-X[0])*(R*R%mo-L*L%mo)%mo*modpow(2);
			}
			else {
				ll e=X[0]*p-X[N-1]*p;
				ll f=e/q;
				ret+=-f*(R-L);
				ret+=-(X[N-1]-X[0])*(R*R%mo-L*L%mo)%mo*modpow(2);
			}
			ret=ret%mo;
		}
	}
	cout<<(ret%mo+mo)%mo*modpow(3)%mo<<endl;
}

まとめ

なんか最近積分を使う問題がちょこちょこ出てきたな…。