石家庄做网站备案有哪些公司,泰国做那个视频网站,百度推广账号登陆入口,扬州网站建设兼职正题
题目链接:https://www.luogu.com.cn/problem/CF622F 题目大意
给出n,kn,kn,k#xff0c;求 ∑i1nik\sum_{i1}^ni^ki1∑nik 解题思路
很经典的拉格朗日差值问题 这个东西显然是可以化成一个k1k1k1次的多项式的#xff0c;所以我可以直接代k2k2k2个点插出值来。看到顺…正题
题目链接:https://www.luogu.com.cn/problem/CF622F 题目大意
给出n,kn,kn,k求 ∑i1nik\sum_{i1}^ni^ki1∑nik 解题思路
很经典的拉格朗日差值问题 这个东西显然是可以化成一个k1k1k1次的多项式的所以我可以直接代k2k2k2个点插出值来。看到顺眼先把n,kn,kn,k互换一下。 先上一个要刻在DNADNADNA里的公式f(k)∑i1nyi∏j1,j≠inxj−kxi−xjf(k)\sum_{i1}^ny_i\prod_{j1,j\neq i}^n\frac{x_j-k}{x_i-x_j}f(k)i1∑nyij1,ji∏nxi−xjxj−k 发现这个直接计算是O(n2)O(n^2)O(n2)的搞不定。 上面的xj−kx_j-kxj−k挺好优化的分别做一个前后缀积就好了但是麻烦的是xi−xjx_i-x_jxi−xj。我们可以利用xix_ixi是连续的这个性质我们只需要带入xi∈[1,n2]x_i\in[1,n2]xi∈[1,n2]的点即可。
此时xi−xjx_i-x_jxi−xj就变为了两段阶乘分别是∏j1i−11i−j\prod_{j1}^{i-1}\frac{1}{i-j}∏j1i−1i−j1和∏ji1j1i−j\prod_{ji1}^j\frac{1}{i-j}∏ji1ji−j1。预处理逆元前缀和就好了需要注意的是因为后面那个式子i−ji-ji−j是负数所以我们需要判断一下如果n−in-in−i是奇数就要取反。
线性筛yiy_iyi的话时间复杂度O(n)O(n)O(n)懒得话直接快速幂O(nlogk)O(n\log k)O(nlogk) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,P1e97;
ll n,k,ans,inv[N],suf[N],pre[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{scanf(%lld%lld,k,n);// if(kn2){// for(ll i1;ik;i)// ans(anspower(i,n))%P;// printf(%d\n,ans);// return 0;// }inv[1]1;n2;for(ll i2;in;i)inv[i]P-(P/i)*inv[P%i]%P;inv[0]1;for(ll i1;in;i)inv[i]inv[i-1]*inv[i]%P;ll tmp1;pre[0]suf[n1]1;for(ll i1;in;i)pre[i]pre[i-1]*(k-i)%P;for(ll in;i1;i--)suf[i]suf[i1]*(k-i)%P;for(ll i1,p0;in;i){(ppower(i,n-2))%P;ansp*pre[i-1]%P*suf[i1]%P*inv[i-1]%P*(((n-i)1)?P-inv[n-i]:inv[n-i])%P;ansans%P;}printf(%lld\n,(ansP)%P);return 0;
}
