C.C.A - 个人主页动态

2022-10-16 14:02

A 观察数据生成器可以发现对于每次操作均有 。 考虑将这些三元组想象成空间直角坐标系中以 和 为对顶点的长方体。 将操作分成两部分，一部分是对 轴同时操作的，可以一开始就用前缀 统计完，将长方体变成一个底面为阶梯状的直棱柱。另一部分是对 或 操作的，考虑从小到大枚举 ，然后将 的操作变成一条横线或一条竖线，容易发现这两条线也是具有单调性的，于是每层留下的点数可以直接计算。 最后用总点数减去剩下的点数即为删除的三元组数量，由于答案最大可能到 ，所以需要使用高精或 __int128。总时间复杂度为 。 #include <bits/stdc++.h> using name...

Wilson_Lee_hitsz：还有第4题代码能加些注释吗？

投递3e等公司8个岗位 >

0 点赞评论收藏

2022-09-10 17:20

湖南师范大学附属中学算法工程师

牛客挑战赛 63 解题报告

牛客挑战赛 63 解题报告 A 考虑从后往前填数，可以发现除了第一个位置之外每个位置都有且仅有两种选择，故答案为 。 时间复杂度可以做到 。 #include <bits/stdc++.h> using namespace std; const int mod = 998244353; int n, fac = 1; int Pow (int a, int k) {     int res = 1;     for (; k; a = 1ll * a * a % mod, k >>= 1)         if (k & 1)...

C.C.A：太离谱了，为啥有两个牛客挑战赛 63 啊，之前发错地方了。

0 点赞评论收藏

2022-03-18 23:23

湖南师范大学附属中学算法工程师

牛客挑战赛 58 解题报告

https://uploadfiles.nowcoder.com/files/20220318/999991351_1647614721258/%E7%89%9B%E5%AE%A2%E6%8C%91%E6%88%98%E8%B5%9B58%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A.pdf

EMT_TPYQ：麻麻我不会多项式差分怎么办？不难注意到 E 题实际上是在计算 $n!\frac{(1-y)^n}{1-e^xy}[x^n][y^n]$ 施加拉格朗日反演可得：$n!\frac{1}{n}(\dfrac{x}{ln(x+1)})\frac{(1-y)^n}{(1-(x+1)y)^2}[x^{n-1}y^n]$ 对于第二部分稍做化简可以得到其实就是 $x^{n-1}$ 不难发现将原式的 $i^n$ 可以换成任意形如 $(1+Ax+B(x))^i[x^n]$，此时答案就是 $A^n * n!$ LaTeX 自行复制后提取，至于 C 的处理，读者可以自行尝试

0 点赞评论收藏