2018-09-09 00:04:40
497
0
0
炉石传说中的期望
同步发表在939499625的qq空间
前言：
作为一门功能性极强的学科，信息学科的竞赛知识经常可以用于解决生活中的一些实际问题。今天，我们就来看一看信息学竞赛在炉石传说中的应用。
在这篇文章中，你将看到如何利用信息学以及概率期望知识分析炉石传说的天梯上分难度。在这之前，我们先了解一些前置知识。
零、概率与期望：
概率相信大家并不陌生，表示一个事件发生的可能性。那么期望是什么呢？简单来说，期望是所有情况下收益的平均值。比如扔一个骰子，有1~6这6个面，一共有6种情况——6个面都可能朝上。于是我们用所有情况的点数和除以情况数得到期望为3.5 。类
【题目描述】给你n个k维0/1向量组成的串a[n]。 定义向量a <= b当且仅当a中每一个1出现的位置在b中都是1 比如{0,1,0,1}<={0,1,0,1}, {0,1,0,1}<={0,1,1,1} 但是{0,1,0,1}和{1,0,0,1}没有这样的关系 现在请你统计这个串中有多少个不下降子序列。 一个子序列是一个1~n组成的序列， 其中每个元素都满足i < j且a[i] <= a[j]。 【输入】第一行两个正整数n，k。n表示串的长度，k表示向量维数 下面n行每一行一个0/1字符串表示一个k维向量 【输出】输出一个整数，表示不下降序列个数。 【输入样例
Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divi
Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list. Input The input contains several test cases. For each test case, there are two lines. The first line
2018-08-18 09:46:59
477
0
0
一、FFT
n次单位根：
wnk=e2πin=cos2πkn+sin2πkni" role="presentation" style="position: relative;">wkn=e2πin=cos2πkn+sin2πkniwnk=e2πin=cos2πkn+sin2πkni w^k_n = e^{\frac{2\pi i}{n}} = cos{\frac{2\pi k}{n}+sin{\frac{2\pi k}{n}i}}
可以证明：
(wnk)n=1" role="presentation" style=
【题目描述】给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。 每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。 每组数据中，第
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could b
【题目描述】
求n个点的有向图的强连通图的个数对998244353取模后得结果(无重边，无自环)
定义强连通图为本身为强连通分量的图
【输入格式】
输入一个n表示点数
【输出格式】
输出题目要求的答案
【样例输入】
2
【样例输出】
1
【提示】
对于30%的数据，n<=1000
对于100%的数据，n<=100000
30分的做法详见：网上一篇很好的博客
这个东西是个卷积形式，很容易想到生成函数。
我们来回顾一下两个式子：
f(n)=g(n)+∑k=0n(n−1k−1)f(k)g(n−k) f(n)=g(n)+\sum^{n}_
【题目描述】
求n个点的有向图中强连通图的个数，输出答案对10007取模后得结果(无重边，无自环)
定义强连通图为本身是一个强连通分量的图
【输入格式】
输入一个n表示节点个数
【输出格式】
输出题目要求的答案
【样例输入】
【样例输出】
【提示】
样例解释：
只有一个图，即有边<1,2>和边<2,1>
对于30%的数据，n<=7
对于100%的数据，n<=1000
几个月之前想过强连通图的计数问题，发现根本不可做，暑假集训突然就变成作业了……
这道题的容斥姿势太高超了，功力不够学不来QWQ。
考虑模仿
小 L 计划进行 n" data-mce-tabindex="0">nn 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。 小 L 的赛车有三辆，分别用大写字母 A、B、C 表示。地图一共有四种，分别用小写字母 x、a、b、c 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 d 张。 n" data-mce-tabindex="0">nn 场游戏的地图可以用一个小写字母组成的字符串描述
Rockdu's Blog