bzoj4944 【NOI2017】泳池

bzoj4944 【NOI2017】泳池

​​从第0行开始连续的 一个矩形 直接求 大小为K 不可求 那么不妨求小于等于K -小于等于K-1的即可 那么设dp[i][j]表示宽度为i 高度至少为j的概率i是多少

那么dp[i][j]=0(i∗j>k)dp[i][j]=1(j==0) d p [ i ] [ j ] = 0 ( i ∗ j > k ) d p [ i ] [ j ] = 1 ( j == 0 )

dp[i][j]=dp[i][j+1]∗bin[i]+∑dp[z][j+1]∗bin[z]∗dp[i−z−1][j]∗(1−p); d p [ i ] [ j ] = d p [ i ] [ j + 1 ] ∗ b i n [ i ] + ∑ d p [ z ] [ j + 1 ] ∗ b i n [ z ] ∗ d p [ i − z − 1 ] [ j ] ∗ ( 1 − p ) ;

最后一个方程可以看做是枚举最左边的一个严格高度等于j的位置 那么为什么要*bin[i] 因为我们相当于是倒推 所以我相当于dp[i][j+1]的值其实并没有算完 那么我在这次继续给他完善而已

后面的30分涉及多项式还没学会

#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int mod=998244353;const int N=1100;inline int ksm(ll b,int t){static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;}inline void inc(int &x,int v){x=x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}int n,k,x,y,p,q;int dp[N],g[N],bin[N];inline int gao(int K){ memset(g,0,sizeof(g));g[0]=1; for (int h=K;~h;--h){ memset(dp,0,sizeof(dp));dp[0]=1; for (int i=1;i<=(h?(K/h):n);++i){ inc(dp[i],(ll)g[i]*bin[i]%mod); for (int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。