#760822 (C++14) No.1938 Lagrange Sum

提出ソース

結果

問題	No.1938 Lagrange Sum
ユーザー	SSRS
提出日時	2022-05-13 23:17:23
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	321 ms / 3,000 ms
コード長	6,335 bytes
コンパイル時間	2,543 ms
コンパイル使用メモリ	190,232 KB
実行使用メモリ	12,500 KB
最終ジャッジ日時	2024-07-22 03:33:39
合計ジャッジ時間	7,859 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	317 ms 12,376 KB
testcase_01	AC	321 ms 12,368 KB
testcase_02	AC	319 ms 12,500 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	218 ms 8,480 KB
testcase_06	AC	247 ms 9,588 KB
testcase_07	AC	4 ms 6,940 KB
testcase_08	AC	83 ms 6,940 KB
testcase_09	AC	35 ms 6,940 KB
testcase_10	AC	313 ms 12,040 KB
testcase_11	AC	87 ms 6,944 KB
testcase_12	AC	316 ms 12,000 KB
testcase_13	AC	316 ms 11,888 KB
testcase_14	AC	151 ms 7,824 KB
testcase_15	AC	25 ms 6,940 KB
testcase_16	AC	295 ms 9,920 KB
testcase_17	AC	148 ms 7,888 KB
testcase_18	AC	150 ms 7,816 KB
testcase_19	AC	312 ms 11,832 KB
testcase_20	AC	315 ms 11,844 KB
testcase_21	AC	15 ms 6,940 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	13 ms 6,940 KB
testcase_24	AC	296 ms 9,920 KB
testcase_25	AC	1 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
long long modpow(long long a, long long b){
	long long ans = 1;
	while (b > 0){
		if (b % 2 == 1){
			ans *= a;
			ans %= MOD;
		}
		a *= a;
		a %= MOD;
		b /= 2;
	}
	return ans;
}
long long modinv(long long a){
	return modpow(a, MOD - 2);
}
vector<long long> ntt(vector<long long> A, bool inv){
	int N = A.size();
	long long r = 3;
	if (inv){
		r = modinv(r);
	}
	vector<long long> B(N);
	for (int i = N / 2; i > 0; i /= 2){
		long long z = modpow(r, (MOD - 1) / (N / i));
		long long z2 = 1;
		for (int j = 0; j < N; j += i * 2){
			for (int k = 0; k < i; k++){
				A[i + j + k] *= z2;
				A[i + j + k] %= MOD;
				B[j / 2 + k] = (A[j + k] + A[i + j + k]) % MOD;
				B[N / 2 + j / 2 + k] = (A[j + k] - A[i + j + k] + MOD) % MOD;
			}
			z2 = z2 * z % MOD;
		}
		swap(A, B);
	}
	if (inv){
		int Ninv = modinv(N);
		for (int i = 0; i < N; i++){
			A[i] = A[i] * Ninv % MOD;
		}
	}
	return A;
}
vector<long long> convolution(vector<long long> A, vector<long long> B, int d = -1){
	int deg = A.size() + B.size() - 1;
	int N = 1;
	while (N < deg){
		N *= 2;
	}
	A.resize(N);
	B.resize(N);
	A = ntt(A, false);
	B = ntt(B, false);
	vector<long long> ans(N);
	for (int i = 0; i < N; i++){
		ans[i] = A[i] * B[i] % MOD;
	}
	ans = ntt(ans, true);
	if (d != -1){
		deg = d;
	}
	ans.resize(deg);
	return ans;
}
vector<long long> diff(vector<long long> A){
  int N = A.size();
  vector<long long> B(N - 1);
  for (int i = 1; i < N; i++){
    B[i - 1] = A[i] * i % MOD;
  }
  return B;
}
vector<long long> polynomial_inverse(vector<long long> f){
  int N = f.size();
  vector<long long> ans(1);
  ans[0] = modinv(f[0]);
  for (int i = 1; i < N * 2; i *= 2){
    vector<long long> ans2 = ans;
    ans2.resize(i * 4);
    int N2 = min(N, i * 2);
    vector<long long> f2(i * 4, 0);
    for (int j = 0; j < N2; j++){
      f2[j] = f[j];
    }
    ans2 = convolution(ans2, ans2, i * 2);
    ans2 = convolution(ans2, f2, i * 2);
    for (int j = 0; j < i; j++){
      ans2[j] = MOD - ans2[j] + ans[j] * 2;
      ans2[j] %= MOD;
    }
    swap(ans, ans2);
  }
  ans.resize(N);
  return ans;
}
vector<long long> polynomial_quotient(vector<long long> f, vector<long long> g){
  int N = f.size(), M = g.size();
  if (N < M){
    return {0};
  }
  reverse(g.begin(), g.end());
  g.resize(N - M + 1);
  vector<long long> t = polynomial_inverse(g);
  reverse(f.begin(), f.end());
  vector<long long> q = convolution(f, t, N - M + 1);
  reverse(q.begin(), q.end());
  return q;
}
vector<long long> polynomial_remainder(vector<long long> f, vector<long long> g){
  int N = f.size();
  int M = g.size();
  if (M <= 1200){
    for (int i = N - M; i >= 0; i--){
      long long q = f[i + M - 1] * modinv(g[M - 1]) % MOD;
      for (int j = 0; j < M; j++){
        f[i + j] += MOD - q * g[j] % MOD;
        f[i + j] %= MOD;
      }
      f.pop_back();
    }
    return f;
  } else {
    vector<long long> q = polynomial_quotient(f, g);
    vector<long long> b = convolution(g, q);
    for (int i = 0; i < N; i++){
      f[i] += MOD - b[i];
      f[i] %= MOD;
    }
    f.resize(M - 1);
    return f;
  }
}
vector<long long> multipoint_evaluation(vector<long long> &f, vector<long long> x){
  int M = x.size();
  int M2 = 1;
  while (M2 < M){
    M2 *= 2;
  }
  vector<vector<long long>> g(M2 * 2 - 1, {1});
  for (int i = 0; i < M; i++){
    g[M2 - 1 + i] = vector<long long>{MOD - x[i], 1};
  }
  for (int i = M2 - 2; i >= 0; i--){
    g[i] = convolution(g[i * 2 + 1], g[i * 2 + 2]);
  }
  g[0] = polynomial_remainder(f, g[0]);
  for (int i = 1; i < M2 * 2 - 1; i++){
    g[i] = polynomial_remainder(g[(i - 1) / 2], g[i]);
  }
  vector<long long> ans(M);
  for (int i = 0; i < M; i++){
    ans[i] = g[M2 - 1 + i][0];
  }
  return ans;
}
long long polynomial_interpolation(vector<long long> x, vector<long long> y, long long a){
  int N = x.size();
  queue<vector<long long>> Q;
  for (int i = 0; i < N; i++){
    Q.push(vector<long long>{MOD - x[i], 1});
  }
  while (Q.size() >= 2){
    vector<long long> f = Q.front();
    Q.pop();
    vector<long long> g = Q.front();
    Q.pop();
    Q.push(convolution(f, g));
  }
  vector<long long> lp = diff(Q.front());
  vector<long long> w = multipoint_evaluation(lp, x);
  long long P = 1;
  for (int i = 0; i < N; i++){
    P *= MOD + a - x[i];
    P %= MOD;
  }
  long long ans = 0;
  for (int i = 0; i < N; i++){
    long long tmp = P;
    tmp *= modinv(MOD + a - x[i]);
    tmp %= MOD;
    tmp *= modinv(w[i]);
    tmp %= MOD;
    ans += tmp * y[i] % MOD;
  }
  ans %= MOD;
  return ans;
}
int main(){
  int N, X;
  cin >> N >> X;
  vector<long long> x(N), y(N);
  for (int i = 0; i < N; i++){
    cin >> x[i] >> y[i];
  }
  int p = -1;
  for (int i = 0; i < N; i++){
    if (x[i] == X){
      p = i;
    }
  }
  if (p != -1){
    vector<long long> x2, y2;
    for (int i = 0; i < N; i++){
      if (i != p){
        x2.push_back(x[i]);
        y2.push_back(y[i]);
      }
    }
    long long ans = polynomial_interpolation(x2, y2, X);
    ans += (long long) (N - 1) * y[p];
    ans %= MOD;
    cout << ans << endl;
  } else {
    queue<vector<long long>> Q;
    for (int i = 0; i < N; i++){
      Q.push(vector<long long>{MOD - x[i], 1});
    }
    while (Q.size() >= 2){
      vector<long long> f = Q.front();
      Q.pop();
      vector<long long> g = Q.front();
      Q.pop();
      Q.push(convolution(f, g));
    }
    vector<long long> lp = diff(Q.front());
    vector<long long> w = multipoint_evaluation(lp, x);
    vector<long long> P(N);
    for (int i = 0; i < N; i++){
      P[i] = modinv(w[i]);
    }
    long long sum1 = 0, sum2 = 0;
    for (int i = 0; i < N; i++){
      sum1 += modinv(X - x[i] + MOD) % MOD;
      sum1 %= MOD;
      sum2 += (MOD - x[i]) * modinv(X - x[i] + MOD) % MOD;
      sum2 %= MOD;
    }
    vector<long long> S(N, 0);
    for (int i = 0; i < N; i++){
      S[i] = (sum1 - modinv(X - x[i] + MOD) + MOD) * x[i] % MOD;
      S[i] += sum2 - (MOD - x[i]) * modinv(X - x[i] + MOD) % MOD;
      S[i] += MOD;
      S[i] %= MOD;
    }
    long long ans = 0;
    for (int i = 0; i < N; i++){
      ans += y[i] * modinv(X - x[i] + MOD) % MOD * P[i] % MOD * S[i] % MOD;
    }
    ans %= MOD;
    for (int i = 0; i < N; i++){
      ans *= X - x[i] + MOD;
      ans %= MOD;
    }
    cout << ans << endl;
  }
}

yukicoder

結果

テストケース

ソースコード