[LibreOJ 6024]XLkxc
转载请注明出处：http://danihao123.is-programmer.com/
拉格朗日插值的模板题qwq
考虑f(n)=∑ni=1ik，这显然是一个k+1次多项式（通过差分之类的手段可以证明），然后我们发现g(n)=∑ni=1f(n)可以用类似手段证明是k+2次多项式。类似的，我们会发现，答案是一个k+3次多项式。
分别对g以及答案插值即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <cctype>#include <algorithm>#include <utility>#include <queue>#include <climits>typedef long long ll;const ll ha = 1234567891LL;int k;ll a, n, d;ll pf[205], pg[205], fac[205];ll pow_mod(const ll &a, ll b) { if(!b) return 1LL; ll ans = pow_mod(a, b >> 1); ans = (ans * ans) % ha; if(b & 1LL) ans = (ans * a) % ha; return ans;}ll inv(ll v) { return pow_mod(v, ha - 2LL);}void process() { fac[0] = 1LL; for(int i = 1; i <= k + 5; i ++) { fac[i] = (fac[i - 1] * inv(i)) % ha;#ifdef LOCAL printf("fac[%d] : %lld\n", i, fac[i]);#endif } for(int i = 1; i <= k + 3; i ++) { pf[i] = (pf[i - 1] + pow_mod(i, k)) % ha;#ifdef LOCAL printf("pf[%d] : %lld\n", i, pf[i]);#endif } for(int i = 1; i <= k + 3; i ++) { pg[i] = (pg[i - 1] + pf[i]) % ha;#ifdef LOCAL printf("pg[%d] : %lld\n", i, pg[i]);#endif }#ifdef LOCAL puts("Processing finished!");#endif}ll g(ll x) { static ll sim_f[205], sim_g[205]; sim_f[0] = 1LL; for(int i = 1; i <= k + 3; i ++) { sim_f[i] = (x - (ll(i)) + ha) % ha; sim_f[i] = (sim_f[i] * sim_f[i - 1]) % ha; } sim_g[k + 4] = 1LL; for(int i = k + 3; i >= 1; i --) { sim_g[i] = (x - (ll(i)) + ha) % ha; sim_g[i] = (sim_g[i] * sim_g[i + 1]) % ha; } ll ret = 0; for(int i = 1; i <= k + 3; i ++) { ll ans = (((pg[i] * sim_f[i - 1]) % ha) * sim_g[i + 1]) % ha; ans = (ans * fac[i - 1]) % ha; ans = (ans * fac[k + 3 - i]) % ha; if(1 & (k + 3 - i)) { ret = (ret - ans + ha) % ha; } else { ret = (ret + ans) % ha; } }#ifdef LOCAL printf("g(%lld) : %lld\n", x, ret);#endif return ret;}ll h(ll x) { static ll ph[205]; ph[0] = g(a); for(int i = 1; i <= k + 4; i ++) { ph[i] = (ph[i - 1] + g(a + (ll(i)) * d)) % ha; } static ll sim_f[205], sim_g[205]; sim_f[0] = 1LL; for(int i = 1; i <= k + 4; i ++) { sim_f[i] = (x - (ll(i)) + ha) % ha; sim_f[i] = (sim_f[i] * sim_f[i - 1]) % ha; } sim_g[k + 5] = 1LL; for(int i = k + 4; i >= 1; i --) { sim_g[i] = (x - (ll(i)) + ha) % ha; sim_g[i] = (sim_g[i] * sim_g[i + 1]) % ha; } ll ret = 0; for(int i = 1; i <= k + 4; i ++) { ll ans = (((ph[i] * sim_f[i - 1]) % ha) * sim_g[i + 1]) % ha; ans = (ans * fac[i - 1]) % ha; ans = (ans * fac[k + 4 - i]) % ha; if(1 & (k + 4 - i)) { ret = (ret - ans + ha) % ha; } else { ret = (ret + ans) % ha; } } return ret;}int main() { int T; scanf("%d", &T); while(T --) { scanf("%d%lld%lld%lld", &k, &a, &n, &d); process(); printf("%lld\n", h(n)); } return 0;} |
3 年前
Twitter Card validator obviously used in Twitter and to know more about the validator. It is merely important to understand about the Twitter Card. In this article, we will come up with details of Twitter Card and Twitter Card validator and different type of cards available to make you understand better along with its usage. twitter card validator Twitter Card goes gives a link between your tweets by adding designed structured look and attracting more audience. In simple terms, the code must add to webpage and when someone shares your tweets link will display as Twitter Card.
3 年前
History is one of the most important subjects for Arts/Humanities Stream PUC I and PUC II students, and Pre University Education subject experts are provided chapter wise study material with practice mock test question paper for History subject to Kannada medium and English medium Arts group students to SA, FA, Term and annual final public examination tests of March to the academic year of 2023. Kar PUC History Question Paper The Pre University Education Arts group students can download chapter wise guess and important questions from KAR PUC History Model Paper 2023.