kmjp's blog

競技プログラミング参加記です

M-SOLUTIONS プロコンオープン : E - Product of Arithmetic Progression

まさかOEISでもWikipediaでもないところのお世話になるとは。
https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e

問題

初項X、公差D、要素数Nの等差数列について、全要素の積を1000003で割った余りを答えよ。

解法

X=0とかD=0とか、Nが1000003以上のようなコーナーケースは先に片づけておく。
「等差数列 積」で検索するとこんな記事が出てくる。
等差数列の和の公式は小学校で習ったけど、等差数列の積の公式はあるんでし... - Yahoo!知恵袋

あとは以下の負の二項係数のところを参考に実装しよう。
二項係数 - Wikipedia

別解というか公式解は下記のとおり。
公差が1であれば階乗値の乗算除算で済む。
そこで、全要素を最初にDで割ろう。そうすると公差1の数列ができる。
その積を求めた後、D^Nを掛ければよい。

int Q;
ll X,D,N;
ll mo=1000003;
const int NUM_=2400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];



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;
}

ll comb(ll a,ll b) {
	//cout<<a<<"!"<<b<<endl;
	a=-a;
	ll ret=fact[a+b-1]*factr[b]%mo*factr[a-1]%mo;
	if(b%2) ret=mo-ret;
	return ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	
	cin>>Q;
	while(Q--) {
		cin>>X>>D>>N;
		
		if(X==0) {
			cout<<0<<endl;
			continue;
		}
		if(D==0) {
			cout<<modpow(X,N)<<endl;
			continue;
		}
		
		ll k=(mo-X)%mo*modpow(D)%mo;
		//cout<<k<<endl;
		if(k<N) {
			cout<<0<<endl;
			continue;
		}
		//cout<<fact[N]<<" "<<modpow(mo-D,N)<<" "<<comb(-X*modpow(D)%mo,N)<<endl;
		ll ret=fact[N]*modpow(mo-D,N)%mo*comb(-X*modpow(D)%mo,N)%mo;
		cout<<ret<<endl;
	}
}

まとめ

こんなんでいいのかなぁという気はする。