懒得码字了:
题目链接: https://www.luogu.com.cn/problem/CF622F
很简单的数论题, 紫题显然是过了些,(不要说...
对于这个式子, 是一个 \(k+1\) 次的多项式, 插 \(k+2\) 次值就好了, 烦人的是处理逆元, 我的费马小定理显然是 \(O(logp)\) 的, 可以用拓欧, 听说还有 \(O(k)\) 的算法, 我似乎感觉不太可能 (我太弱了).
预处理处阶乘, 前, 后缀积数组即可, 复杂度 \(O(klogk+klogp)\), 可以通过此题 (跑得飞快. jpg).
- \(Code:\)
- #include<iostream>
- #include<cstdio>
- #define mod 1000000007
- using namespace std;
- long long n,k;
- long long fac[1000005],y[1000005];
- long long pre[1000005],suf[1000005];
- long long ans=0;
- long long quickpow(long long a,long long b)
- {
- long long base=a,ans=1;
- while(b)
- {
- if(b&1) ans=1ll*base*ans%mod;
- b>>=1;
- base=1ll*base*base%mod;
- }
- return ans%mod;
- }
- inline int judge(long long x){if(x&1) return -1;else return 1;}
- int main()
- {
- scanf("%lld%lld",&n,&k);
- if(!k)
- {
- printf("%lld\n",n);
- return 0;
- }
- if(n<=k+2)
- {
- for(long long i=1;i<=n;i++) ans=(ans+quickpow(i,k))%mod;
- printf("%lld\n",ans%mod);
- return 0;
- }
- fac[0]=1,y[0]=0;
- pre[0]=1,suf[k+3]=1;
- for(int i=1;i<=k+1;i++) fac[i]=1ll*fac[i-1]*i%mod;
- for(int i=1;i<=k+2;i++) y[i]=(y[i-1]+quickpow(i,k))%mod;
- for(int i=1;i<=k+1;i++) pre[i]=1ll*pre[i-1]*(n-i)%mod;
- for(int i=k+2;i>1;i--) suf[i]=1ll*suf[i+1]*(n-i)%mod;
- for(int i=1;i<=k+2;i++)
- {
- long long sum=1;
- sum=fac[i-1]*fac[k+2-i]*judge(k+2-i)%mod;
- if(judge(k+2-i)==1) sum=1ll*quickpow(sum,mod-2);
- else sum=-1ll*(quickpow(-sum,mod-2));
- sum=(sum+mod)*y[i]%mod;
- sum=sum*pre[i-1]%mod;
- sum=sum*suf[i+1]%mod;
- ans=(ans+sum)%mod;
- }
- printf("%lld\n",ans%mod);
- return 0;
- }
没开 \(long long\) 爆掉了
(我还知道 \(O(k^3)\) 的做法呢)---- 差分法, 可以拿部分分, 比正解还高深 \(qwq\).
来源: http://www.bubuko.com/infodetail-3415383.html