?

牛客網(wǎng)暑期ACM多校訓(xùn)練營(第一場(chǎng)) F?Sum?of Maximum

杜教板子：

證明https://blog.csdn.net/Lee_w_j__/article/details/81135539

#include <cstdio> #include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <map> #include <set> #include <list> #include <cmath> #include <cstring> #include <queue> #include <stack> #include <ctime> #include <complex> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define forn(i,n) for(int i = 0;i<n;i++) #define for1(i,n) for(int i = 1;i<=n;i++) #define pb push_back //#define mp make_pair #define all(x) (x).begin(),(x).end() //#define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef long double ld; typedef pair<int,int> PII; typedef pair<ll,ll> PLL; typedef unsigned us; typedef unsigned long long ull; const ll mod=1e9+7; const int inf = 1000000000; const int maxn = 1003005; const int maxa = 300005; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} ll powmod(ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int INF = 10000000; //ll fac(ll a) {ll ans = 1;for(int i = 1;i<=a;i++) ans*=i;return a==0?1:ans;}; //start = clock(); //finish = clock(); //cout<<double(finish - start) / CLOCKS_PER_SEC<<" seconds"<<endl; //rep(i,2,100002) inv[i] = inv[mod%i]*(mod-mod/i)%mod; // clock_t start,finish; //double duration; //long double eps = 1e-10;//You wanna hack this? Are you Serious?namespace polysum {const int D=3001000;ll a[D],f[D],g[D],p[D],p1[D],p2[D],b[D],h[D][2],C[D];ll calcn(int d,ll *a,ll n) {if (n<=d) return a[n];p1[0]=p2[0]=1;rep(i,0,d+1) {ll t=(n-i+mod)%mod;p1[i+1]=p1[i]*t%mod;}rep(i,0,d+1) {ll t=(n-d+i+mod)%mod;p2[i+1]=p2[i]*t%mod;}ll ans=0;rep(i,0,d+1) {ll t=g[i]*g[d-i]%mod*p1[i]%mod*p2[d-i]%mod*a[i]%mod;if ((d-i)&1) ans=(ans-t+mod)%mod;else ans=(ans+t)%mod;}return ans;}void init(int M) {f[0]=f[1]=g[0]=g[1]=1;rep(i,2,M+5) f[i]=f[i-1]*i%mod;g[M+4]=powmod(f[M+4],mod-2);per(i,1,M+4) g[i]=g[i+1]*(i+1)%mod;}ll polysum(ll n,ll *a,ll m) { // a[0].. a[m] \sum_{i=0}^{n-1} a[i]a[m+1]=calcn(m,a,m+1);rep(i,1,m+2) a[i]=(a[i-1]+a[i])%mod;return calcn(m+1,a,n-1);}ll qpolysum(ll R,ll n,ll *a,ll m) { // a[0].. a[m] \sum_{i=0}^{n-1} a[i]*R^iif (R==1) return polysum(n,a,m);a[m+1]=calcn(m,a,m+1);ll r=powmod(R,mod-2),p3=0,p4=0,c,ans;h[0][0]=0;h[0][1]=1;rep(i,1,m+2) {h[i][0]=(h[i-1][0]+a[i-1])*r%mod;h[i][1]=h[i-1][1]*r%mod;}rep(i,0,m+2) {ll t=g[i]*g[m+1-i]%mod;if (i&1) p3=((p3-h[i][0]*t)%mod+mod)%mod,p4=((p4-h[i][1]*t)%mod+mod)%mod;else p3=(p3+h[i][0]*t)%mod,p4=(p4+h[i][1]*t)%mod;}c=powmod(p4,mod-2)*(mod-p3)%mod;rep(i,0,m+2) h[i][0]=(h[i][0]+h[i][1]*c)%mod;rep(i,0,m+2) C[i]=h[i][0];ans=(calcn(m,C,n)*powmod(R,n)-c)%mod;if (ans<0) ans+=mod;return ans;} } ll n,k,R; ll a[maxn]; int main() {ios::sync_with_stdio(0);cin>>n>>R>>k;for(int i = 0;i<=2010;i++) a[i] = powmod(i,k);polysum::init(k+5);ll ans = 0;ans = polysum::qpolysum(R,n+1,a,k+1);if(k==0) ans = (ans-1+mod)%mod;cout<<ans<<endl;}

不是我說dls也太強(qiáng)了吧，，隨便一個(gè)namespace全世界都在用。。。

總結(jié)

以上是生活随笔為你收集整理的拉格朗日差值 - 杜教板子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。