插值
當A確定，這就是一個關于ｎ的多項式，并不知道為什么．反正直接拉格朗日插值．
#include<cstdio>#define N 2333using namespace std;namespace runzhe2000{ typedef long long ll; int A, n, mod, y[N], f[N][N], frombig[N], fromsma[N], fac[N]; int fpow(int a, int b) { int r = 1; for(; b; b>>=1) { if(b&1)r = (ll) r * a % mod; a = (ll) a * a % mod; } return r; } void la() { fac[0] = 1; for(int i = 1; i <= 2*n+10; i++) fac[i] = (ll) fac[i-1] * i % mod; fromsma[0] = 1; frombig[2*n+10+1] = 1; for(int i = 1; i <= 2*n+10; i++) { frombig[2*n+10 - i + 1] = (ll) frombig[2*n+10 - i + 2] * (A - (2*n+10 - i + 1)) % mod; fromsma[i] = (ll) fromsma[i-1] * (A - i) % mod; } int ans = 0, tmp; for(int i = 1; i <= 2*n+10; i++, (ans += tmp) %= mod) { tmp = (ll) fromsma[i-1] * frombig[i+1] % mod; tmp = (ll) tmp * y[i] % mod; tmp = (ll) tmp * fpow(fac[i-1], mod - 2) % mod; tmp = (ll) tmp * fpow((i&1)?-fac[2*n+10-i]:fac[2*n+10-i], mod - 2) % mod; }新聞熱點
疑難解答
