正題

題目鏈接:https://www.luogu.com.cn/problem/P7116

---

題目大意

有一個(gè)$k$維空間，第$i$維長(zhǎng)度為$w_i$，有$n$步每一步都是讓某個(gè)維的坐標(biāo)$+1/?1$，每次走完$n$步都會(huì)從$1$重新走一次，現(xiàn)在求從這個(gè)空間的每個(gè)點(diǎn)出發(fā)走多少步才能走出這個(gè)空間的步數(shù)的和。

$1\le n\le 5\times 10^5$

$1\le k\le 10,1\le w_i\le 10^6$ 或者 $1\le k\le 3,1\le w_i\le 10^9$

---

解題思路

求在這一步出去的方案顯然很麻煩，所以我們可以考慮對(duì)于每步之后求還沒(méi)出去的起點(diǎn)數(shù)然后求個(gè)和就一樣了。并且每個(gè)維度可以在一定程度上分開(kāi)考慮。

第一輪顯然需要特別處理，設(shè)$l_{i,j},r_{i,j}$表示第$i$步之后第$j$維的最小位移（非正數(shù)）和最大位移，那么這一步不會(huì)出去的方案就是${\prod }_{j=1}^k(w_j?r_{i,j}+l_{i,j})$，也就是在$[1?l,w?r]$這個(gè)范圍可以存活，這個(gè)可以暴力處理。

之后考慮每輪的第$i$步的最小/最大位移距離依舊記作$l_{i,j},r_{i,j}$，之后考慮如何計(jì)算每一步多少輪之后會(huì)死亡，記作$t$。

首先設(shè)$a_i$表示第一輪維度$i$縮小的范圍，然后$b_i$表示之后每一輪這個(gè)維度縮小的范圍，那么對(duì)于第$i$步來(lái)說(shuō)，第$j$個(gè)維度的最久存活輪數(shù)就是$?\frac{a_j?r_{i,j}+l_{i,j}}{b_j}?$，算出$t$之后假設(shè)如果我們能夠枚舉輪數(shù)的話那么答案應(yīng)該就是
$$\sum _{x=1}^t\prod _{j=1}^k{a}_j?r_{i,j}+l_{i,j}?b_{j}x$$
顯然可以$O(k^2)$暴力乘算得到一個(gè)和$x$有關(guān)的多項(xiàng)式然后求和。

至于多項(xiàng)式求和我們可以通過(guò)${\sum }_{x=0}^t{x}^j$帶入多項(xiàng)式暴算，可以直接拉插得到，當(dāng)然這題可以對(duì)于$k\le 3$的情況我們自己手動(dòng)插多項(xiàng)式算，然后$k>3$的就直接預(yù)處理就好了。

時(shí)間復(fù)雜度：$O(n{k}^2)$ 或者 $O(n{k}^2+k\times max\{w_i\})$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10,M=11,P=1e9+7; ll n,m,ans,pw[M][N*2],l[N][M],r[N][M],w[M],a[M],b[M],e[M],f[M][M]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } ll calc(ll n,ll k){if(k>3)return pw[k][n];if(k==3)return (n*(n+1)/2%P)*((n*(n+1)/2)%P)%P;if(k==2)return n*(n+1)%P*(2*n+1)%P*((P+1)/6)%P;if(k==1)return n*(n+1)/2%P; return n+1; } signed main() {scanf("%lld%lld",&n,&m);for(ll k=4;k<=m;k++)for(ll i=1;i<=1e6;i++)pw[k][i]=(pw[k][i-1]+power(i,k))%P;ans=1;for(ll i=1;i<=m;i++)scanf("%lld",&w[i]),ans=ans*w[i]%P;for(ll i=1;i<=n;i++){ll c,d;scanf("%lld%lld",&c,&d);e[c]+=d;for(ll j=1;j<=m;j++)l[i][j]=l[i-1][j],r[i][j]=r[i-1][j];l[i][c]=min(l[i][c],e[c]);r[i][c]=max(r[i][c],e[c]);}bool flag=1;for(ll i=1;i<=m;i++)if(e[i]!=0||w[i]-r[n][i]+l[n][i]<=0){flag=0;break;}if(flag)return puts("-1")&0;for(ll i=1;i<=n;i++){ll sum=1;for(ll j=1;j<=m;j++)sum=sum*max(0ll,w[j]-r[i][j]+l[i][j])%P;ans=(ans+sum)%P;}for(ll i=1;i<=m;i++)a[i]=w[i]-r[n][i]+l[n][i];for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){l[i][j]=min(0ll,l[i][j]+e[j]-l[n][j]);r[i][j]=max(0ll,r[i][j]+e[j]-r[n][j]);}for(ll i=1;i<=m;i++)b[i]=r[n][i]-l[n][i];flag=0;for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++)f[0][j]=0;f[0][0]=1;ll t=1e9+7;for(ll j=1;j<=m;j++){ll x=a[j]-r[i][j]+l[i][j];if(x<=0){flag=1;break;}if(b[j]>0)t=min(t,x/b[j]);for(ll k=0;k<=m;k++){(f[j][k]=f[j-1][k]*x%P)%=P;if(k)(f[j][k]+=f[j-1][k-1]*(P-b[j])%P)%=P;}}if(flag)break;for(ll j=0;j<=m;j++)(ans=ans+f[m][j]*calc(t,j)%P)%=P;}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7116-[NOIP2020]微信步数【数学】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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