动态线性基可以维护一个集合,支持修改集合元素,并查询子集最大异或和。
给定 和 ,满足 ,求出在 维空间中从 走到 ,每一步使某一维坐标增加 的方案中随机选出一种,满足经过的所有点 都满足 的概率,答案模 输出。 。
有一张顶点数为 的有向图。这张图的每个顶点由一个二元组表示。
这张图不是简单图,对于任意两个顶点 ,如果 ,则从 到 一共有 条不同的边,如果 则没有边。 白兔将在这张图上上演一支舞曲。白兔初始时位于该有向图的顶点 。 白兔将会跳若干步。每一步,白兔会从当前顶点沿任意一条出边跳到下一个顶点。白兔可以在任意时候停止跳舞(也可以没有跳就直接结束)。当到达第一维为 的顶点就不得不停止,因为该顶点没有出边。 假设白兔停止时,跳了 步,白兔会把这只舞曲给记录下来成为一个序列。序列的第 个元素为它第 步经过的边。 问题来了:给定正整数 和 (),对于每个 (),求有多少种舞曲(假设其长度为 )满足 ,且白兔最后停在了坐标第二维为 的顶点? 两支舞曲不同定义为它们的长度()不同或者存在某一步它们所走的边不同。 。