「LOJ 2304」「NOI2017」泳池

发表于

久莲是个爱玩的女孩子。

暑假终于到了，久莲决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

经过初步分析，这块海域可视为一个底边长为 NN 米，高为 10011001 米的长方形网格。其中网格的底边对应着她家的私人海滩，每一个 1m×1m1m\times 1m 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后，她要做的就是圈出她想要的游泳场啦。

她心目中理想的游泳场满足如下三个条件：

  • 必须保证安全性。即游泳场中的每一个单位海域都是安全的。
  • 必须是矩形。即游泳场必须是整个网格中的一个 a×ba\times b 的子网格。
  • 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。

为了让朋友们玩的开心，她想让游泳场的面积尽可能的大。

虽然她要明天才能知道每一个单位海域是否安全，但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计，她假设每一个单位海域都有独立的 qq 的概率是安全的， 1−q 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积恰好为 KK 的概率是多少。

然而久莲对数学并不感兴趣，因此她想让你来帮她计算一下这个数值。

avatar

Constraints

n≤109n \leq 10^9 ， K≤1000K \leq 1000

Solution

转化问题为求游泳场面积小于 KK 的概率，最终答案为 K+1K+1 的计算结果减去 KK 的计算结果。

令 f(i,j)f(i,j) 表示长为 ii ，每一行高度至少为 jj ，且满足条件的概率。可得：

f(i,j)={0(i⋅j≥K)f(i,j+1)+qj⋅(1−q)⋅∑k=0i−1f(k,j+1)⋅f(i−k−1,j)(i⋅j<K)f(i,j) = \begin{cases} 0 & (i\cdot j \ge K)\\ f(i,j+1)+q^j\cdot (1-q)\cdot \sum_{k=0}^{i-1} f(k,j+1)\cdot f(i-k-1,j) & (i \cdot j < K) \end{cases}

特殊地，当 i=0i=0 时， f(i,j)=1f(i,j)=1 。

计算结果即为 f(n,0)f(n,0) ，时间复杂度 O(nklogk)O(nklogk) ，可以通过 70 分，下面放出的代码也是 70 分的代码。

对于接下来的分数，因为当 i≥Ki\ge K 时，只有 f(i,0)f(i,0) 的值不为 00 ，所以当 i>=Ki>=K 时有式子：

f(i,0)=(1−q)⋅∑k=0K−1f(k,1)⋅f(i−k−1,0)f(i,0) = (1-q)\cdot \sum_{k=0}^{K-1} f(k,1)\cdot f(i-k-1,0)

然后……先屯着了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e3+5;
const int mod=998244353;
int n,m,x,y,q,K;
int ans,tmp,mi[N],f[N][N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;b>>=1;
	}
	return ans;
}
int inv(int x){return power(x,mod-2);}
void Mod(int& a,int b){a+=b;if(a>=mod)a-=mod;}
void work()
{
	memset(f,0,sizeof(f));
	for(int i=0;i<=K;i++)f[0][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=(K-1)/i;j>=0;j--)
		{
			f[i][j]=f[i][j+1];
			for(int k=0;k<=i-1;k++)
				Mod(f[i][j],1ll*(mod+1-q)*mi[j]%mod*f[k][j+1]%mod*f[i-k-1][j]%mod);
		}
	ans=f[n][0];
}
int main()
{
	n=read();m=read();x=read();y=read();
	q=1ll*x*inv(y)%mod;
	mi[0]=1;for(int i=1;i<=m+1;i++)mi[i]=1ll*mi[i-1]*q%mod;
	K=m;work();tmp=(mod-ans)%mod;
	K=m+1;work();Mod(ans,tmp);
	printf("%d",ans);
	return 0;
}