這道題目數據有坑,白浪費一個小時!
題意:求\(\sum_{i=1}^n\sum_{j=1}^n{|i-j|+k \choose k}\)
知識點: 朱世杰恒等式,\(\sum_{i=r}^n{i \choose r}={n+1 \choose r+1},r<n\)
題解:首先去除式子中的絕對值,考慮對稱性還有i=j時的重復,原式可轉化為\(2\sum_{i=1}^n\sum_{j=i}^n{j-i+k \choose k}-n\)
對式子內部循環調用一遍朱世杰恒等式\(\sum_{j=i}^n{j-i+k \choose k}=\sum_{j=k}^{k+n-i}{j \choose k}={{k+n-i+1} \choose {k+1}}\) (對中間式子有疑惑的可自行展開)
再對外部循環調用一遍\(\sum_{i=1}^n{{k+n-i+1} \choose {k+1}}=\sum_{i=k+1}^{k+n}{i \choose {k+1}}={{k+n+1} \choose {k+2}}\)

福利:\(\sum_{i=m}^n{i \choose r}={n+1 \choose r+1}-{m \choose r+1}\)

#include<bits/stdc++.h> #define rep(i,j,k) for(int i=j;i<=k;i++) using namespace std; typedef long long ll; const ll mod = 1000000007; const int maxn = 2e6+111; ll jie[maxn],inv[maxn]; ll fpw(ll a,ll n){ll ans=1;while(n){if(n&1) ans=(ans*a)%mod;n>>=1; a=(a*a)%mod;}return ans; } ll C(ll n,ll k){ll up=jie[n];ll down=inv[k]*inv[n-k]%mod;return (up*down)%mod; } int main(){ll T; scanf("%lld",&T);jie[0]=inv[0]=1;rep(i,1,maxn-2) jie[i]=(jie[i-1]*i)%mod;rep(i,1,maxn-2) inv[i]=fpw(jie[i],mod-2);while(T--){ll n,k; scanf("%lld%lld",&n,&k);ll tmp=C(n+k+1,k+2);ll ans=((tmp*2)%mod-n+mod)%mod;printf("%lld\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/caturra/p/8454713.html

總結

以上是生活随笔為你收集整理的CodeChef - NWAYS 组合数 朱世杰恒等式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。