多項式插值 盡量別用快速冪

#include <iostream>

using namespace std;
typedef long long ll;
const ll N = 3000;

ll p,dp[N][N];
ll f[N]={1},t[N],ans[N],inv[N];
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> p;
    for(int i = 0; i < p; i++) cin >> dp[1][i];
    for(int i = 1; i < p; i++) for(int j = 1; j <= i; j++) if(i*j%p==1) inv[i]=j, inv[j]=i;
    for(int L = 2; L <= p; L++) {
        for(int i = 0; i+1 < p; i++) {
            dp[L][i] = (dp[L-1][i+1] - dp[L-1][i] + p) * inv[L-1] % p;
        }
    }
    for(int i = 0; i < p; i++) {
        for(int j = 0; j < p; j++) ans[j] = (ans[j]+dp[i+1][0]*f[j])%p;
        t[0] = (p-i)*f[0]%p;
        for(int j = 1; j < p; j++) t[j] = (f[j-1] - i*f[j]%p + p)%p;
        for(int j = 0; j < p; j++) f[j] = t[j];
    }
    for(int i = 0; i < p; i++) cout << ans[i] << " \n"[i==p-1];
}