BZOJ 2655 calc

2019-11-10 16:52:42

字体：大中小

来源：转载

供稿：网友

插值

当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; } PRintf("%d/n",(ans+mod)%mod); } void main() { scanf("%d%d%d",&A,&n,&mod); f[0][0] = 1; for(int i = 1; i <= 2*n+10; i++) { f[i][0] = 1; for(int j = 1; j <= 2*n+10; j++) f[i][j] = (f[i-1][j] + (ll) f[i-1][j-1] * j % mod * i % mod) % mod; } for(int i = 1; i <= 2*n+10; i++) y[i] = f[i][n]; la(); }}int main(){ runzhe2000::main();}

上一篇：专题五-队列

下一篇：数据结构实验之二叉树七：叶子问题