Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Lagrange Interpolation

コードについての説明

ラグランジュ補間とは n 次多項式 f と n+1 個の異なる引数についての関数値が与えられたときに元の多項式 f を決定する手法のことをいう. 以下の実装では MOD を法として n 次多項式 f の値 f[0]∼f[n] が与えられたときに f[num] の値を返すアルゴリズムとなっている.
実際に o(n2) 時間で f の係数まで決定するアルゴリズムについてはこちらの実装を参考にされたい.

時間計算量: O(n) (n は多項式の次数)

コード

  1. #define MAX_N 100005
  2. #define MOD 1000000007
  3.  
  4. unsigned inv[MAX_N], fac[MAX_N], finv[MAX_N];
  5.  
  6. unsigned int add(unsigned int x, unsigned int y){
  7. 	return (x + y >= MOD) ? (x + y - MOD) : (x + y);
  8. }
  9.  
  10. unsigned int sub(unsigned int x, unsigned int y){
  11. 	return (x < y) ? (x + MOD - y) : (x - y);
  12. }
  13.  
  14. unsigned int mul(unsigned int x, unsigned int y){
  15. 	return (unsigned long long)x * y % MOD;
  16. }
  17.  
  18. void make()
  19. {
  20. 	fac[0] = fac[1] = 1;
  21. 	finv[0] = finv[1] = 1;
  22. 	inv[1] = 1;
  23. 	for(int i = 2; i < MAX_N; ++i){
  24. 		inv[i] = MOD - mul(inv[MOD % i], (MOD / i));
  25. 		fac[i] = mul(fac[i - 1], i);
  26. 		finv[i] = mul(finv[i - 1], inv[i]);
  27. 	}
  28. }
  29.  
  30. // solve() を呼び出す前に必ず make() を行っておく！！
  31. // deg + 1 個の f(i) = val[i] (i = 0,..., deg) の情報から関数 f を復元し, f(num) を返す
  32. // すべて MOD を法として考えていることに注意
  33. unsigned int solve(int deg, long long num, vector<int>& val)
  34. {
  35. 	if((num %= MOD) < 0) num += MOD;
  36. 	if(num <= deg) return val[num];
  37. 	vector<unsigned int> lf(deg + 2), rg(deg + 2);
  38. 	lf[0] = rg[deg + 1] = 1;
  39. 	for(int i = deg; i >= 0; --i){
  40. 		rg[i] = mul(rg[i + 1], num - i);
  41. 	}
  42. 	unsigned int ans = 0;
  43. 	for(int i = 0; i <= deg; ++i){
  44. 		unsigned int r = mul(finv[deg-i], finv[i]);
  45. 		if((deg - i) % 2) r = MOD - r;
  46. 		ans = add(ans, mul(mul(lf[i], rg[i + 1]), mul(r, val[i])));
  47. 		lf[i + 1] = mul(lf[i], num - i);
  48. 	}
  49. 	return ans;
  50. }

verify 用の問題

Codeforces : The Sum of the k-th Powers 提出コード
Atcoder : 見たことのない多項式 提出コード