3042b什么意思_XC3042

3042b什么意思_XC3042Loj #3042. 「ZJOI2019」麻将

大家好,又见面了,我是你们的朋友全栈君。

Loj #3042. 「ZJOI2019」麻将

题目描述

九条可怜是一个热爱打麻将的女孩子。因此她出了一道和麻将相关的题目,希望这题不会让你对麻将的热爱消失殆尽。

1.png

今天,可怜想要打麻将,但是她的朋友们都去下自走棋了,因此可怜只能自己一个人打。可怜找了一套特殊的麻将,它有 \(n(n \ge 5)\) 种不同的牌,大小分别为 \(1\)\(n\),每种牌都有 \(4\) 张。

定义面子为三张大小相同或者大小相邻的麻将牌,即大小形如 \(i, i, i(1 \le i \le n)\) 或者\(i, i + 1, i + 2(1 \le i \le n − 2)\)。定义对子为两张大小相同的麻将牌,即大小形如 \(i, i(1 \le i \le n)\)

定义一个麻将牌集合 \(S\) 是胡的当且仅当它的大小为 \(14\) 且满足下面两个条件中的至少一个:

\(S\) 可以被划分成五个集合 \(S_1\)\(S_5\)。其中 \(S_1\) 为对子,\(S_2\)\(S_5\) 为面子。

\(S\) 可以被划分成七个集合 \(S_1\)\(S_7\),它们都是对子,且对应的大小两两不同

举例来说,下列集合都是胡的(这儿只标记了大小):

\(\{1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9\}\)

\(\{1, 1, 2, 2, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8\}\)

\(\{1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7\}\)

而下列集合都不是胡的:

\(\{1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9\}\)

\(\{1, 1, 1, 1, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8\}\)

\(\{1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 11\}\)

可怜先摸出了 \(13\) 张牌,并把剩下的 \(4n − 13\) 张牌随机打乱。打乱是等概率随机的,即所有 \((4n − 13)!\) 种排列都等概率出现。

对于一个排列 \(P\),可怜定义 \(S_i\) 为可怜事先摸出的 \(13\) 张牌加上 \(P\) 中的前 \(i\) 张牌构成的集合,定义 \(P\) 的权值为最小的 \(i\) 满足 \(S_i\) 存在一个子集是胡的。如果你对麻将比较熟悉,不难发现 \(P\) 的权值就是理论上的最早胡牌巡目数。注意到 \(n \ge 5\) 的时候,\(S_{4n−13}\) 总是存在胡的子集的,因此 \(P\) 的权值是良定义的。

现在可怜想要训练自己的牌效,因此她希望你能先计算出 \(P\) 的权值的期望是多少。

\(\\\)

神仙的\(DP\)\(DP\)题。

首先想如何判断一个局面是胡的。对于第一种胡牌方式,我们用\(DP\)来维护。设\(f_{i,j,k,0/1}\)表示是考虑了前\(i\)种麻将,以\(i-1\)开头的面子有\(j\)个,以\(i\)开头的面子有\(k\)个,是否有对子的最大面子数。注意这里以\(i-1\)开头以及以\(i\)开头的面子都是还没有生效的,要放了大小为\(i+1\)的麻将后才能判断。转移的时候就枚举第\(i\)张牌放入了\(x\)个,枚举几种情况就好了。

对于第二种胡牌方式,直接记\(cnt\)表示不同的顺子个数就行了。

显然\(cnt\)不能达到\(7\)\(f_{i,j,k,1}\)的最大值不能达到\(4\)。于是我们就暴力将\(cnt\)以及\(f\)数组作为状态。如果\(f\)超过\(4\),就存成\(4\)\(cnt\)同理,以减小状态量。可以算出合法状态最多\(2091\)个。

然后就是\(DP\)计数了。设\(F_{i,j,S}\)表示考虑了前\(i\)种麻将,一共摸了\(j\)张牌,\(DP\)状态为\(S\)还未胡牌的概率。转移的时候枚举额外摸了多少张\(i\)麻将(除去底牌)。

我们的定义是还未胡牌而不是已经胡牌的原因是我们枚举的麻将顺序是编号,不是模到这张牌的时间,所以对于一个胡牌的局面,我们不知道他到底是什么时候胡的。

利用一个经典的期望转概率的公式就可以算出答案了:
\[ E=\sum i*P(x=i)\\ =\sum P(x\geq i) \]
代码:

#include<bits/stdc++.h>
#define ll long long
#define N 105
#define M 405

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=998244353;
ll ksm(ll t,ll x) {
    ll ans=1;
    for(;x;x>>=1,t=t*t%mod)
        if(x&1) ans=ans*t%mod;
    return ans;
}
ll fac[M],ifac[M];
ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
struct info {
    int f[3][3][2];
    int cnt;
    info() {memset(f,-1,sizeof(f));f[0][0][0]=cnt=0;}
    bool operator <(const info &a)const {
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<2;k++)
                    if(f[i][j][k]!=a.f[i][j][k]) return f[i][j][k]<a.f[i][j][k];
        return cnt<a.cnt;
    }
    bool chk() {
        if(cnt>=7) return 0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                if(f[i][j][1]>=4) return 0;
        return 1;
    }
    info trans(int x) {
        info tem;
        tem.cnt=cnt+(x>=2);
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                for(int k=0;k<2;k++) {
                    if(f[i][j][k]==-1) continue ;
                    for(int t=0;t<3&&i+j+t<=x;t++) {
                        tem.f[j][t][k]=max(tem.f[j][t][k],f[i][j][k]+i+(x-i-j-t>=3));
                    }
                    if(!k) {
                        for(int t=0;t<3&&i+j+t<=x-2;t++) {
                            tem.f[j][t][1]=max(tem.f[j][t][1],f[i][j][k]+i);
                        }
                    }
                }
            }
        }
        for(int k=0;k<2;k++)
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    tem.f[i][j][k]=min(tem.f[i][j][k],4);
        return tem;
    }
};

int n;
map<info,int>id;
info mj[4005];
int tot;
int Had[N];
info tem;
int trans[4005][5];
void dfs(info now) {
    if(!now.chk()) return ;
    id[now]=++tot;
    mj[tot]=now;
    for(int i=0;i<=4;i++) {
        info tem=now.trans(i);
        if(id.find(tem)==id.end()) dfs(tem);
        trans[id[now]][i]=id[tem];
    }
}

ll f[N][M][2100];
int main() {
    fac[0]=1;
    for(int i=1;i<=400;i++) fac[i]=fac[i-1]*i%mod;
    ifac[400]=ksm(fac[400],mod-2);
    for(int i=399;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    info x;
    dfs(x);
    n=Get();
    
    for(int i=1;i<=13;i++) {
        int w=Get(),t=Get();
        Had[w]++;
    }
    
    f[0][0][1]=1;
    for(int i=0;i<n;i++) {
        for(int j=0;j<=i*4;j++) {
            for(int k=1;k<=tot;k++) {
                if(!f[i][j][k]) continue ;
                for(int t=Had[i+1];t<=4;t++) {
                    if(trans[k][t]) (f[i+1][j+t-Had[i+1]][trans[k][t]]+=f[i][j][k]*C(4-Had[i+1],t-Had[i+1])%mod*C(j+t-Had[i+1],t-Had[i+1])%mod*fac[t-Had[i+1]])%=mod;
                }
            }
        }
    }
    
    ll ans=0;
    for(int i=0;i<=4*n-13;i++) {
        for(int j=1;j<=tot;j++) {
            (ans+=f[n][i][j]*ifac[4*n-13]%mod*fac[4*n-13-i])%=mod;
        }
    }
    cout<<ans;
    
    return 0;
}

转载于:https://www.cnblogs.com/hchhch233/p/10821757.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/106837.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • oracle 查看所有表和视图

    oracle 查看所有表和视图查看所有表:select*fromall_tables查看所有视图:select*fromall_views

  • Offline Explorer_手机chrome离线网页

    Offline Explorer_手机chrome离线网页提及离线浏览软件,我想大家都知道“元老级”的TeleportPro吧?一些网友可能还挺怀念的,毕竟它开了离线浏览之先河,为广大网友节省了不少银子,带来了不少便利,功不可没呵!然而时过境迁,“江山代有才人出”,一大批新的离线浏览软件登场了。这里我要向大家介绍的是一个设计全新的离线浏览软件——OfflineExplorer1.1。一、基本信息 OfflineExplorer1.1由MetaP…

  • 程序员为什么不喜欢去做外包_外包程序员的出路

    程序员为什么不喜欢去做外包_外包程序员的出路做IT的一定对于外包公司很熟悉,就算没做过,想必也是经常听说,说实话在行业内是存在鄙视链的,而外包公司往往在最低端。很多人都在四处问:“软件外包公司到底能不能去”?到底能不能学到真正的技术?我来为大家详细梳理一下这个问题。想要知道外包公司到底值不值得去,我们就应该了解外包公司的概念是什么?不仅仅是IT行业有软件外包公司,在很多行业中,外包公司的数量也都是最多的。外包的工作形式分为两种:‍外包公司承接甲方的项目,了解需求后拿回自己的公司做项目,程序员按照客户的需求把代码写好,最终完成项目,外包

  • 剑指java面试offer直通车_面试后一般多久给offer

    剑指java面试offer直通车_面试后一般多久给offer这是本人整理的数万字的面试笔记,基本上涵盖了Java领域的所有技术栈,本人也是凭借这份面试笔记斩获了近10个offer,面试成功率高达80%。当然这份笔记是我根据自身的经验和技术栈整理的,自己觉得很重要的或者记不清的就会记录记录下来,面试被问到的时候也有回答的思路。现在共享给大家,希望对准备面试的小伙伴有帮助。1.微服务1.1主流注册中心对比zookeeper:zookeeper作为注册中心主要是因为它具有节点变更通知功能。只要客户端监听相关服务节点,服务节点有所变更就能及时的通知到监

  • 洛谷p2669_洛谷首页

    洛谷p2669_洛谷首页洛谷 2577 [ZJOI2005]午餐——序列dp

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号