まさか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; } }
まとめ
こんなんでいいのかなぁという気はする。