• 等级
  • 404612 访问
  • 1200 原创
  • 3 转发
  • 1265 排名
  • 162 评论
  • 117 获赞

LibreOJ #2271.「SDOI2017」遗忘的集合 多项式ln

题意给出一个n次多项式f(x)f(x)f(x),求一个范围在1到n之间的正整数集合S使得系数在模p意义下有f(x)≡∏11−xSi(modxn+1)f(x)\equiv\prod\frac{1}{1-x^{S_i}}\pmod{x^{n+1}}f(x)≡∏1−xSi​1​(modxn+1)n≤218n\le2^{18}n≤218分析我们设f(x)=∏i=1n(11−xi)hif(...

2019-02-13 22:25:52

51nod 1514 美妙的序列 多项式求逆

题意某个1~n的排列如果满足:在1~n-1这些位置后面将序列断开,使得总可以从右边找到一个数,并且该数不大于左边的所有数,则称该序列为“美妙的”。给出n,求长度为n的“美妙的序列”的数量。n≤105n\le10^5n≤105分析不难得到递推式fn=n!−∑i=1n−1fi(n−i)!f_n=n!-\sum_{i=1}^{n-1}f_i(n-i)!fn​=n!−i=1∑n−1​f...

2019-02-12 13:20:21

洛谷P3711 仓鼠的数学题 伯努利数

题意设Sk(x)=∑i=0xikS_k(x)=\sum_{i=0}^xi^kSk​(x)=i=0∑x​ik给出n和a0,...,ana_0,...,a_na0​,...,an​,求∑k=0nSk(x)ak\sum_{k=0}^nS_k(x)a_kk=0∑n​Sk​(x)ak​其中答案是一个n+1n+1n+1次多项式且定义00=10^0=100=1。n≤250000n\le250...

2019-02-12 12:00:24

伯努利数学习小记

伯努利数伯努利数的定义如下:B0=1∑k=0n(n+1k)Bk=0B_0=1\\\sum_{k=0}^{n}\dbinom{n+1}{k}B_k=0B0​=1k=0∑n​(kn+1​)Bk​=0知道定义后我们就可以O(n2)O(n^2)O(n2)来递推求伯努利数。生成函数考虑伯努利数的指数型生成函数B(x)=∑k≥0Bkk!B(x)=\sum_{k\ge0}\frac{B_k...

2019-02-11 14:15:02

LibreOJ #6268. 分拆数 生成函数+多项式exp

题意求1到n的分拆数。n=105n=10^5n=105分析设分拆数的生成函数为F(x)=∑i=1nf(i)xiF(x)=\sum_{i=1}^nf(i)x^iF(x)=i=1∑n​f(i)xi显然有F(x)=∏k=1n11−xkF(x)=\prod_{k=1}^n\frac{1}{1-x^k}F(x)=k=1∏n​1−xk1​两边取对数得ln⁡F(x)=∑i=1nln⁡11−x...

2019-02-10 17:13:59

Codeforces 438E The Child and Binary Tree 生成函数+牛顿迭代

题意考虑一个含有n个互异正整数的序列c[1],c[2],…,c[n]。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合{c[1],c[2],…,c[n]}中,我们的小朋友就会将其称作神犇的。并且他认为,一棵带点权的树的权值,是其所有顶点权值的总和。给出一个整数m,你能对于任意的s(1<=s<=m)计算出权值为s的神犇二叉树的个数吗?请参照样例以更好的理解什么样的两棵二叉树会被...

2019-02-09 18:09:03

UOJ #139.【UER #4】被删除的黑白树 长链剖分

题意给出一棵有根树,要求对尽量多的节点染色,使得每个叶节点到根的路径上的染色节点数都相等。n≤105n\le10^5n≤105分析开始刷水题了。。。设dp[i,j]表示以i为根的子树中每个叶节点到i路径上的染色点数恰好为j时的答案,用长链剖分优化转移就是O(n)O(n)O(n)的了。代码#include<iostream>#include<cstdio>#...

2019-02-07 17:36:04

UOJ #455.【UER #8】雪灾与外卖 堆模拟费用流

题意有n个人和m家商店,每个人都要买一道菜。第i个人的坐标是a[i],第j家商店的坐标是y[i],有c[i]道菜且每道菜价格为w[i],每个人还要花费其到商店距离的路费,问最小花费。n,m≤105,a[i],y[i],c[i],w[i]≤109n,m\le10^5,a[i],y[i],c[i],w[i]\le10^9n,m≤105,a[i],y[i],c[i],w[i]≤109分析显然可以...

2019-02-07 15:45:39

NOIP2018 保卫王国 动态dp

题意有一棵n个点的树,在每个点上放士兵都有一个花费a[i],要求每相邻的两个点之间至少有一个点要放士兵。有m个询问,每个询问会固定两个点的选择,然后问最小花费。n,m≤105n,m\le10^5n,m≤105分析设fi,0/1f_{i,0/1}fi,0/1​表示以iii为根的子树,iii放或不放士兵的最小花费。考虑一条链要怎么做。显然有fi,0=fi−1,1fi,1=ai+min(f...

2019-02-07 12:19:00

UOJ #454.【UER #8】打雪仗 通信题

题意有两个人Alice和Bob,现在Alice有一个长度为2n的01串,Bob有n个位于[1,2n]之间的下标,现在要求Alice和Bob之间传递信息,每次只能发送0或1,要求每人发送次数不超过m,且Bob能知道这n个下标对应的字符是什么。n=1000,m=2000或1600或1350。分析m=2000当然就是Alice直接把整个串发过去啦。考虑这样一种做法,设Bob的长度为2n的01串...

2019-02-06 11:46:54

UOJ #449.【集训队作业2018】喂鸽子 min-max容斥

题意有n只鸽子,每个时刻会等概率随机给某只鸽子喂食,若一只鸽子被喂食的次数不小于k次则已饱。问期望多少个时刻之后每只鸽子都已饱。n≤50,k≤1000n\le50,k\le1000n≤50,k≤1000分析先min-max容斥一下转成求E(min(ti))E(min(t_i))E(min(ti​))。然后问题变成求前m个盒子恰好有一个被放了k个球的期望时间。设这m个盒子总共放了x个球,...

2019-02-05 10:29:55

superguymj的thuwc2019游记

thuwc2019游记(我是superguymj,因为没有blog,所以就发到这来了。感谢beginend的友情铺位)day0晚上日常上分之后有点兴奋,结果十点多躺在床上睡不着,起来听了会儿歌就已经12点了。day1早上七点多起的,感觉并不是很困。驾车到达广二是9点多,根据指引找到了报道处。这次有四种颜色的衣服,都是外套,分别是红蓝灰黑。但每个人只能拿一件。我还没说话,工作人员就塞了一件...

2019-01-26 19:33:52

UOJ #395. 【NOI2018】你的名字 后缀自动机

题意给一个串S,每次询问给出一个串T和区间[l,r],问T中有多少个不同的子串满足其不是S[l…r]的子串。∣S∣,∣T∣≤5∗105,q≤105,∑∣T∣≤106|S|,|T|\le5*10^5,q\le10^5,\sum|T|\le10^6∣S∣,∣T∣≤5∗105,q≤105,∑∣T∣≤106分析在noi考场上打了个又臭又长的做法,还只有68分。正解其实并不算难。先补集转化一下,...

2018-10-14 16:22:50

Codeforces 98E Help Shrek and Donkey 纳什均衡

题意有n+m+1张牌,牌上的数字互不相同且均在[1,n+m+1]中。A有n张牌,B有m张牌,还有一张牌盖在桌上。现在A和B轮流操作,当前操作的那一方有两种操作:猜盖在桌上的牌是什么,若猜对则直接获胜,猜错则直接输。猜一张对方的手牌,若猜对则对方需要把该牌扔掉,猜错则没有影响。假设双方都绝顶聪明,问先手获胜的概率是多少。n,m≤1000n,m\le1000n,m≤1000分析想看比较详...

2018-10-04 12:30:21

AtCoder Regular Contest 103 F - Distance Sums 构造

题意给出n和一个长度为n的数组d,满足d数组中的任意两个元素互不相同,要求构造一棵n个节点边权为1的树,使得所有节点到节点i的距离和恰好为d[i]。n≤100000n\le100000n≤100000分析显然按d[i]排序之后,要么从小到大构造,要么从大到小构造。由于d[i]互不相同,不难发现d[i]最小的一定是重心,d[i]最大的一定是叶子。由于一棵树中除了根以外每个节点只有一个父亲...

2018-10-01 22:19:40

牛客练习赛27 B-手办 乱搞

题意给出nnn,设f(x)f(x)f(x)表示有多少个有序数对(a,b)(a,b)(a,b)满足ab∣xab|xab∣x。求∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1n​f(i)。n≤1012n\le10^{12}n≤1012分析看完题目就开始推式子,不难得到答案就是∑i=1n⌊ni⌋σ0(i)\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\s...

2018-09-24 11:44:30

牛客网Wannafly挑战赛24 D-无限手套 生成函数

题意有n种物品,每种物品有两个参数ai,biai,bia_i,b_i。现在可以从每种物品中选出若干个,设第i种物品选了xixix_i个,则贡献∏i=1n(aix2+bix+1)∏i=1n(aix2+bix+1)\prod_{i=1}^n(a_ix^2+b_ix+1)有q次询问,每次询问给出一个m,求所有选的物品总数为m的选择方案的贡献和,答案模998244353。n,q≤1000,m≤...

2018-09-15 17:31:51

Codeforces 1037H Security 后缀自动机+线段树

题意给一个长度为n的字符串s,有q次询问,每次询问给出一个区间和一个字符串t,求区间中字典序最小的子串使得该子串的字典序大于t。n≤105,q≤2∗105n≤105,q≤2∗105n\le10^5,q\le2*10^5。分析无聊模版题。先预处理出sam上的right集线段树,枚举答案串和t的lcp长度,再枚举下一个字符是什么,然后直接在线段树上查找即可。时间复杂度O(n...

2018-09-09 17:25:23

牛客网Wannafly挑战赛23 F-计数 矩阵树定理+拉格朗日插值法

题意给出一个n个点m条边的带权无向图,问有多少棵生成树满足边权和模k等于0,答案模p输出。n,k≤100,p≤109,p为质数且满足k≡1(modp)n,k≤100,p≤109,p为质数且满足k≡1(modp)n,k\le100,p\le10^9,p为质数且满足k\equiv1\pmodp。分析一种直观的套路就是把每条边的边权看成是xwxwx^w,然后做矩阵树定理,最后得出来...

2018-09-09 16:13:42

AtCoder Regular Contest 102 题解

前言开学之后估计就没办法打比赛了。开场做掉A和B之后,C写了个NTT结果被卡常,然后就一直卡到快比赛结束,这时突然发现第二个生成函数只用预处理到一半!在还有两分钟结束的时候成功卡过,怒涨了一波rating。。。题解C-TriangularRelationship乱做。。。代码#include<iostream>#include<cstd...

2018-09-01 23:54:38

SFN1036

本人单身,一般不坑
关注
  • 中学生
  • 中国 广东省 东莞市
奖章
  • 持之以恒
  • 1024超级勋章