首页 > 其他分享 >2023.8.7模拟

2023.8.7模拟

时间:2023-08-10 19:58:32浏览次数:42  
标签:prod int pow3 sum leq 2023.8 id 模拟

T1

Description

Solution

Code

点击查看

T2

Description

Solution

Code

点击查看

T3

Description

Solution

Code

点击查看

T4 抽卡I([THUPC2023决赛]老hu机)

link:https://www.luogu.com.cn/problem/P9379

Description

俺のターン,ドロー!(然后对面就翻开神宣把你拍出去的神抽无效了

但是出题人玩Honkai,导致背景和yugioh毛关系没有……

一共有\(n\)种卡,每种卡的编号是一个长度为\(l\)的\(01\)串,读入十进制数\(a_i\)表示。

可以进行一次操作,有\(p_i\)的概率得知第\(i\)位的值,\(1-p_i\)的概率得不到,读入\(c_i = p_i \times 10^4\)表示。

一旦能确定是哪张卡就停止,问每一张卡确定的期望操作数。

答案对\(998244353\)取模。多测。

\(1 \leq T \leq 10, 1 \leq l \leq 15,1 \leq n \leq 2^l, 1 \leq c_i \leq 10^4, 0 \leq a_i < 2^l\)

Solution

前言:记得分清小写S\(p\)下角标不同所代表的含义不同,还有大小写的\(p\)(懒,不想改了

首先关注到通过若干操作得出的已确定的位置集合\(A\)。当\(A\)可以确定目标卡片时,称\(A\)合法。

期望值经典trick是通过期望的线性性求出每个合法状态\(S\)的概率\(P_S\),乘上停留在该状态的期望时间\(t_S\),再全部求和。

注意到合法集\(A\)的超集也是合法的,因此无论目标串和停留时间是多少,都不影响\(P_S\)

设\(p_S\)为停留在\(S\)状态的概率,那么\(p_S = \prod\limits_{i \not\in S}(1-p_i)\)(全都不告诉你,老倒霉蛋了)。

又因为另一个经典trick,\(t_S = \sum\limits p_S^x = \frac{1}{1-p_S}\),即操作若干次仍停留在状态\(S\),显然收敛于\(\frac{1}{1-p_S}\)

接下来考虑从\(P_S\)到\(P_T\)的转移系数,即\(\frac{\prod_{i \in T }\prod_{i \not\in T(1-p_i)\wedge i \not\in S}p_i}{1-z_S}\),即不在状态\(T\)的不动,在\(T\)却不在\(S\)的状态必须动。可以通过预处理转移集合\(S\)需要动元素动的概率\(f_S = \prod_{i \in S} p_i\)与转移集合\(S\)的总概率\(g_S = f_S\prod_{i \not\in S}(1-p_i)\),这样系数就可以写成\(\frac{g_T}{f_S-g_S}\)。之后就是平平无奇的枚举超集\(dp\),\(O(3^l)\)(当然按位处理可以做到\(O(l2^l)\),不过不影响)。

该预处理的都处理完了,接下来就是计算答案。对于目标串\(s_i\),设\(T_i\)表示能确定串\(s_i\)的所有合法集合\(A\),则如前文,对于\(s_i\)的答案为\(\sum_{A \not\in T_i}P_At_A\)。

对于任意的\(A\),它不会出现在超过\(2^{|A|}\)个集合\(T_i\)中。因此\(\sum T_i \leq 3^l\)。所以我们就可以进行容斥(补集转化:好歹用一下集合名词啊),将答案写成\(\sum_A P_At_A - \sum_{A \in T_i}P_At_A\)。所有\(A\)的\(Pt\)和可以在预处理时就求出,那么剩下的就是求\(T_i\)了。

设\(h_{S,T}\)表示位置集合为\(S\)时,状态为\(T\)的唯一串标号,如果没有值为\(0\),有多个值为\(-1\)。初始化\(h_{U,s_i} = i\),\(U\)表示全集,即\(\{0,1,...,l-1\}\)。\(h_S\)能够从\(h_{S \cup \{x\}}\),\(x\)为任意一个不在\(S\)中的位置。如果\(h_{S,T} = i\),就把s_i的答案减\(P_St_S\)。

后记:我本以为wjz已经写的很详细了,没想到他已经写的尽可能精简了。(同时谴责Bronya19C的偷懒行为

Code

点击查看
#include<bits/stdc++.h>
using namespace std;

const int MaxN = 14348917, Mod = 998244353;

int pow3[20] = {1}, p[20];
int lowbit[MaxN], id[MaxN], rev[MaxN];
int val[1<<15|10], f[1<<15|10][16];

long long powM(long long a, int t = Mod-2) {
  long long ret = 1;
  while (t) {
  	if (t&1) ret = ret*a%Mod;
  	a = a*a%Mod; t >>= 1;
  } return ret;
}

void init() {
  int x;
  for (int i = 1; i <= 15; ++i) pow3[i] = pow3[i-1]*3;
  for (int i = 0; i < pow3[15]; ++i) {
  	lowbit[i] = -1, x = i;
  	for (int j = 0; j < 15; ++j, x /= 3)
  		if (x%3 == 2) {
  			lowbit[i] = j;
  			break;
  		}
  	if (~lowbit[i]) rev[i] = rev[i-pow3[lowbit[i]]*2]|1<<lowbit[i];
  }
}

int main() {
  int T, l, n;
  init();
  scanf("%d", &T);
  while (T --) {
  	scanf("%d%d", &l, &n);
  	for (int i = 0; i < l; ++i) {
  		scanf("%d", &p[i]);
  		p[i] = p[i]*powM(10000)%Mod;
  	}
  	memset(f, 0, sizeof(f));
  	val[0] = 1;
  	int sum = 0;
  	for (int s = 0; s < (1<<l); ++s) {
  		auto update = [&]() {
  			for (int i = 0; i < l; ++i) {
  				if (s&(1<<i)) f[s][i+1] = (f[s][i+1]+f[s][i])%Mod;
  				else {
  					f[s|(1<<i)][i+1] = (f[s|(1<<i)][i+1]+1ll*f[s][i]*p[i]%Mod)%Mod;
  					f[s][i+1] = (f[s][i+1]+1ll*f[s][i]*(1-p[i]+Mod)%Mod)%Mod;
  				}
  			}
  		};
  		update();
  		if (s) val[s] = f[s][l];
  		else val[s] = 1;
  		int pp = 1;
  		for (int i = 0; i < l; ++i)
  			if ((~s)&(1<<i)) pp = 1ll*pp*(1-p[i]+Mod)%Mod;
  		int inv = powM(1-pp+Mod);
  		memset(f[s], 0, sizeof(f[s]));
  		f[s][0] = 1ll*val[s]*inv%Mod;
  		update();
  		val[s] = 1ll*val[s]*inv%Mod;
  		sum = (sum+val[s])%Mod;
  	}
  	memset(id, 0, sizeof(id));
  	int x, xx;
  	for (int i = 1; i <= n; ++i) {
  		scanf("%d", &xx);
  		x = 0;
  		for (int j = l; j >= 1; --j) x += pow3[j-1]*((xx&(1<<(j-1)))?1:0);
  		id[x] = i;
  	}
  	vector<int> ans(n+1);
  	for (int s = 1; s < pow3[l]; ++s) {
  		if (~lowbit[s]) {
  			int u = id[s-pow3[lowbit[s]]], v = id[s-pow3[lowbit[s]]*2];
  			if (u == -1 || v == -1 || (u != 0) && (v != 0)) id[s] = -1;
  			else id[s] = u|v;
  		}
  		if (id[s] > 0) ans[id[s]] = (ans[id[s]]+val[rev[s]^((1<<l)-1)])%Mod;
  	} for (int i = 1; i <= n; ++i) printf("%d\n", (sum-ans[i]+Mod)%Mod);
  }
  return 0;
}

Sumary

标签:prod,int,pow3,sum,leq,2023.8,id,模拟
From: https://www.cnblogs.com/BlackCrow/p/17619360.html

相关文章

  • 2023.8.10-格律诗乐器的生产流程和质量控制流程
    一、格律诗乐器说明格律诗乐器是一种独特的音乐器乐,广泛用于传统音乐演奏和文化活动中。在制作格律诗乐器时,生产流程和质量控制是非常重要的环节。本文将详细介绍格律诗乐器的生产流程和质量控制流程,以确保乐器的制作质量和音乐效果的卓越性。二、格律诗乐器的生产流程格律诗乐......
  • 【考后总结】8 月 CSP-S 模拟赛 3
    8.10CSP模拟17BohemianRhapsody-QueenIsthisthereallife?Isthisjustfantasy?Caughtinalandslide,noescapefromrealityOpenyoureyes,lookuptotheskiesandseeI'mjustapoorboy,IneednosympathyBecauseI'measycome,eas......
  • 疯狂模拟四V我165分总结
    模拟4总结目录模拟4总结总体上个体上:第一题:第二题没看第三题老师布置的题目:第四题,eZ题目总体上个人感觉这一次做题非常舒服,第一题和第四题都想出来了,只可惜第三题做对了一点(最大值)个体上:第一题:很可惜,tarjan写错了,实际得分是65分......说明算法流程不是很掌握确实tarjan容......
  • CSP模拟-17
    前言仔细想了想,考试的时候其实对正解有些思路,但自己认为正确性有问题,所以没这么写,大寄,考了倒2,呜呜呜┭┮﹏┭┮T1弹珠游戏下面的匹配的含义:\(R\)的匹配指\(G,B\),其中\(R\)为被匹配字母,\(G,B\)为匹配字母;\(G\)的匹配指\(R,B\)以此类推。我们用把每个人现在手里的牌用十......
  • 2023.8.10-格律诗乐器的生产流程和质量控制流程
    应王建民老师的要求,要求观看王志文主演的电视剧《天道》,重点观看格律诗乐器的生产流程,如何控制质量,对于格律诗乐器的生产流程和质量控制流程有以下总结和感想。格律诗乐器的生产流程:主要为王庙村扶贫、农户式生产、半成品,购买乐圣等公司的配件,在北京进行组装等。在王庙村进行扶......
  • 2023.8.9
    今天比较肝,但是好像还有事情没做完看了科四,觉得这些题还不是很难今天下午涂了石膏娃娃库洛米真的很不错啦!!!就是细节太多了有点累人呜呜明天最后一天了,后天就要去考科四了,加油!!极限备考 ......
  • 2023.8.9 做题记录
    CF20C题意:输出\(1\simn\)的最短路路径。分析:直接裸bfs记录松弛操作的上一个点即可。复盘:不需要复盘。CF840B题意:给出若干条边,对于每个点给出\(d_i=0/1/-1\),若\(d_i=1\)则表示该点度数为奇数,若\(d_i=0\)则表示该点度数为偶数,若\(d_i=-1\)则表示该点度数无限制,请......
  • 2023.8.9 练习
    ARC063E首先树是二分图。二分图同侧的点奇偶性必须相同,异侧必须不同。排掉不合法之后。然后我们处理出若只考虑子树,一个点的取值范围。若一个点没法取值,也排掉。然后从根开始构造即可。ARC062F牛题。首先求点双。若不在点双里面的边,贡献是\(K\).考虑一个点双,若这个点双......
  • 2023.8.89周三:输入带空格的字符串
    1.#include<string>strings;getline(cin,s);2.#include<cstring>#include<stdio.h>chara[1024];gets(a);intlen=strlen(a);//得到数组的实际长度//!!!!!!!!!!!!!!注:cin和getline不能连着用,中间需要加一个cin.ignore;......
  • 堆优化模拟退火(List-Based Simulated Annealing|List-Based SA|LBSA|模拟退火) 算法
    堆优化模拟退火(List-BasedSimulatedAnnealing)算法引入堆优化模拟退火(List-BasedSimulatedAnnealing,简称LBSA)是一种对模拟退火的优化算法。由Shi-huaZhan,[1],[2]JuanLin,[1:1]Ze-junZhang,[1:2]Yi-wenZhong[1:3],[2:1]提出。(以下我们以求最小值为例)解释我们......