題目描述

有一個長為\(n\)，高為1001的網(wǎng)格，每個格子有\(p\)的概率為1，\((1-p)\)的概率0，定義一個網(wǎng)格的價值為極大的全一矩形，且這個矩形的底要貼著網(wǎng)格的底，求這個網(wǎng)格的價值為\(K\)的概率。

題解

我們可以考慮設(shè)一個\(dp\)。

我們定義每一列的高度為這一列最高的位置滿足這個位置及以下的位置都為1。

設(shè)\(dp[i][j]\)表示已經(jīng)做到了前\(i\)列，此時最低的位置為\(j\)并且此時的最大價值不超過\(K\)的概率。

可以看出這是一個前綴和的形式，我們需要在最外面用\(K\)的答案減去\(K-1\)的答案來得到最終的答案。

那么我們的\(dp\)轉(zhuǎn)移可以枚舉最靠前的一列滿足\(j+1\)處是0的列。

那么轉(zhuǎn)移為：

\(dp[i][j]=[i\times j\leq K](1-p)p^j\sum_{x=1}^i\Bigl( (\sum_{k\geq j+1}dp[x-1][k])\times(\sum_{l\geq j}dp[i-x][l])\Bigr)\)

我們要求的答案為\(dp[n][0]\)。

后面的兩個求和部分可以發(fā)現(xiàn)是一個后綴和形式，考慮用后綴和優(yōu)化轉(zhuǎn)移。

比如說我們已經(jīng)算完了等號右邊的部分，我們可以把它加到\(dp[i][l](l\leq j)\)就可以了。

前面枚舉\(i\)，然后枚舉\(K/i\)，再去枚舉\(i\)，總的復(fù)雜度為\(K^2\)。

我們發(fā)現(xiàn)\(n?\)非常大，所以我們需要發(fā)現(xiàn)一些別的性質(zhì)。

發(fā)當(dāng)\(n\geq k\)時，第二維只能為0，所以我們令\(g[n]=dp[n][0]\)。

\[ g[n]=(1-p)\sum_{i=1}^{i\leq K+1}dp[i-1][1]\times g[n-i] \]

\[ g[n]=\sum_{i=1}^{i\leq K+1}(dp[i-1][1]\times (1-p))\times g[n-i] \]
這樣我們把它轉(zhuǎn)化為一個\(K+1\)次的常系數(shù)齊次線性遞推。

可以用矩陣乘法優(yōu)化為\(O(K^3logn)\),期望得分90，使用多項式取模可以優(yōu)化至\(O(K^2logn)\sim(KlogKlogn)\)期望得分100。

注意特判\(K=0\)。

代碼

#include<iostream> #include<cstdio> #include<cstring> #define N 1009 using namespace std; typedef long long ll; const int mod=998244353; int pos,k,n; ll tmp[N<<1],p[N],dp[N][N],P,y,now[N],num[N],ans[N]; inline ll rd(){ll x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } inline ll power(ll x,ll y){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans; } inline void MOD(ll &x){while(x>=mod)x-=mod;} inline void mul(ll *a,ll *b,ll *c){for(int i=0;i<=2*pos;++i)tmp[i]=0; for(int i=0;i<pos;++i)for(int j=0;j<pos;++j)(tmp[i+j]+=a[i]*b[j]%mod)%=mod;for(int i=2*pos-2;i>=pos;--i){for(int j=0;j<pos;++j)tmp[i-pos+j]=(tmp[i-pos+j]-tmp[i]*p[j]%mod+mod)%mod;tmp[i]=0;}for(int i=0;i<pos;++i)c[i]=tmp[i]; } inline ll calc(int k){if(!k){return power(1-P+mod,n);} memset(dp,0,sizeof(dp));memset(num,0,sizeof(num));memset(ans,0,sizeof(ans));for(int i=0;i<=k+1;++i)dp[0][i]=1;for(int i=1;i<=k;++i)for(int j=0;i*j<=k;++j){ll sum=0;for(int x=1;x<=i;++x)(sum=sum+dp[x-1][j+1]*dp[i-x][j]%mod)%=mod;sum=sum*power(P,j)%mod*(1+mod-P)%mod;for(int x=0;x<=j;++x)(dp[i][x]+=sum)%=mod;}k++;pos=k;for(int i=1;i<=k;++i)now[i]=dp[i-1][1]*(mod+1-P)%mod;for(int i=1;i<=k;++i)p[k-i]=mod-now[i];num[1]=1;ans[0]=1;int nn=n;while(nn){if(nn&1)mul(ans,num,ans);mul(num,num,num);nn>>=1;}ll res=0;for(int i=0;i<k;++i)MOD(res+=ans[i]*dp[i][0]%mod);return res; } int main(){n=rd();k=rd();P=rd();y=rd();P=P*power(y,mod-2)%mod;printf("%lld",(calc(k)-calc(k-1)+mod)%mod);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ZH-comld/p/10461183.html

總結(jié)

以上是生活随笔為你收集整理的[NOI2017]泳池的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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