列表

详情

NC17904. [NOI2017]泳池

描述

久莲是个爱玩的女孩子。 暑假终于到了，久莲决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一 块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些 地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。 经过初步的分析，她把这块海域抽象成了一个底边长为 N 米，高为 1001 米的长方 形网格。其中网格的底边对应着她家的私人海滩，每一个 1 × 1 的小正方形都代表着 一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之 后，她要做的就是圈出她想要的游泳场啦。
 她心目中理想的游泳场满足如下三个条件：
• 必须保证安全性。即游泳场中的每一个单位海域都是安全的。 
• 必须是矩形。即游泳场必须是整个网格中的一个 a × b 的子网格。 
• 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。
 例如：当 N = 5 时，若测量的结果如下（因为 1001 太大，这儿只画出网格最下面 三行的信息，其他部分都是危险的）。
 
那么她可以选取最下面一行的 1 × 4 的子海域，也可以选择第三列的 3 × 1 的子海 域。注意她不能选取最上面一行的 1 × 5 的子海域，因为它没有与海滩相邻。 为了让朋友们玩的开心，她想让游泳场的面积尽可能的大。因此她会选取最下面那 一行的 1 × 4 的子海域作为最终方案。 虽然她要明天才能知道每一个单位海域是否安全，但是她现在就想行动起来估计 一下她的游泳场面积有多大。经过简单的估计，她假设每一个单位海域都有独立的 q 的概率是安全的，1 − q 的概率是不安全的。她想要知道她能选择的最大的游泳场的面 积恰. 好. 为 K 的概率是多少。 然而久莲对数学并不感兴趣，因此她想让你来帮她计算一下这个数值。

输入描述

输入一行四个正整数 N, K, x, y，其中 1 ≤ x < y < 998244353。q 的取值为 。 

输出描述

输出一行一个整数表示答案在模 998244353 意义下的取值。即设答案化为最简分式后的形式为  ，其中 a 和 b 的互质。输出整数 x 使得 bx ≡ amod 998244353 且 0 ≤ x < 998244353。可以证明这样的整数 x 是唯一的。 

示例1

输入: 

10 5 1 2

输出: 

342025319

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 579ms, 内存消耗: 8444K, 提交时间: 2019-01-07 18:56:12 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int K=1009;
const ll md=998244353;

ll n,k,p,q,x,y;
ll f[K][K],g[K],powq[K],ans[K];
ll a[K],b[K];

inline ll qpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)
            ret=ret*a%md;
        a=a*a%md;
        b>>=1;
    }
    return ret;
}

inline void mul(ll *a,ll *b,int k)
{
    static ll c[K*2];
    memset(c,0,sizeof(c));
    for(int i=0;i<=k;i++)
        if(a[i])
            for(int j=0;j<=k;j++)
                (c[i+j]+=a[i]*b[j]%md)%=md;
    for(int i=k*2;i>=k+1;i--)
        if(c[i])
            for(int j=1;j<=k+1;j++)
                (c[i-j]+=c[i]*g[j]%md)%=md;
    memcpy(a,c,sizeof(a[0])*(k+1));
}

inline ll solve(int k)
{
    if(!k)return qpow(1-q,n);
    memset(f,0,sizeof(f));
    f[k+1][0]=1;

    for(int j=k;j>=1;j--)
    {
        f[j][0]=1;
        int mi=min((int)n,k/j);
        int ml=min(mi-1,k/(j+1));
        for(int l=0;l<=ml;l++)
            g[l]=f[j+1][l]*powq[l]%md*p%md;
        for(int i=1;i<=mi;i++)
        {
            int ml=min(i-1,k/(j+1));
            for(int l=0;l<=ml;l++)
                (f[j][i]+=g[l]*f[j][i-1-l]%md)%=md;
            (f[j][i]+=f[j+1][i]*powq[i])%=md;
        }
    }   

    ans[0]=1;
    for(int i=1;i<=k+1;i++)
        g[i]=f[1][i-1]*powq[i-1]%md*p%md;
    for(int i=1;i<=k;i++)
    {
        ans[i]=f[1][i]*powq[i]%md;
        for(int j=1;j<=i;j++)
            (ans[i]+=ans[i-j]*g[j])%=md;
    }

    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    a[1]=1;b[0]=1;

    int pcnt=n;
    while(pcnt)
    {
        if(pcnt&1)
            mul(b,a,k);
        mul(a,a,k);
        pcnt>>=1;
    }

    ll ret=0;
    for(int i=0;i<=k;i++)
        (ret+=b[i]*ans[i]%md)%=md;

    return ret;
}

int main()
{
    scanf("%lld%lld%lld%lld",&n,&k,&x,&y);
    x%=md;y%=md;
    q=x*qpow(y,md-2)%md;
    p=(y-x)*qpow(y,md-2)%md;
    powq[0]=1;
    for(int i=1;i<=k;i++)
        powq[i]=powq[i-1]*q%md;
    printf("%lld\n",(solve(k)-solve(k-1)+md)%md);
    return 0;
}

上一题

© 2025 nowcoder.com