https://atcoder.jp/contests/abc335

G - Discrete Logarithm Problems

长度n数组a, 质数$p$

1
2
3

for i in 1..n:
	for j in 1..n:
		ans += 存在k使得  ai.pow(k) \equiv aj \pmod{p}

求 ans

n 2e5

$p \in [2,10^{13}]$

$a_i \in [1,p)$

5s

1024mb

我的思路

首先什么时候会不存在不等

$a_i^k\equiv a_j\pmod{p}$

而注意到例如$1$ 只能得到$1$,而$p-1$只能得到$-1,1$

回忆到64位的miller robin 判别法的过程

需要考虑的是 幂次是$p-1$的 因子 的幂次,也就是$a^t\equiv 1 \pmod{p}$

例如对于7来说

1
2
3
4
5
6

1 (1)
2->4->1 (3)
3->2->6->4->5->1 (6, ntt中会选择的)
4->2->1 (3)
5->4->6->2->3->1 (6)
6->1 (2)

p有10^13，可以暴力 sqrt(p) 分解p-1

然后 通过从小到大尝试 p-1的因子的幂次 是否

可以O(n * log(p) * log(p))计算出每个 ai 的最小幂次x,使得ai^x = 1 \mod p

对于长度 p-1的 肯定是全 可以 贡献N

问题是 长度更小的呢，如何知道哪些可以，哪些不行

$t(a_i) =$最小的幂次使得$a_i^{t}\equiv 1\pmod p$

那么对于成立的 $a_i^k\equiv a_j\pmod{p}$

有$k\le t(a_i)$

$a_i^{kt(a_j)}\equiv a_j^{t(a_j)}\equiv 1\pmod{p}$

$kt(a_j) =wt(a_i), w\in\mathbb{Z}^+$

$\displaystyle k\frac{t(a_j)}{\gcd(t(a_j),t(a_i))} =w\frac{t(a_i)}{\gcd(t(a_j),t(a_i))}, w\in\mathbb{Z}$

$k$是$\displaystyle \frac{t(a_i)}{\gcd(t(a_j),t(a_i))}$的倍数 且 $\le t(a_i)$

好像量级还是没啥变化

另外$1\equiv (a_i^{t(a_i)})^k\equiv (a_i^{k})^{t(a_i)} \equiv a_j^{t(a_i)} \pmod{p}$

所以如果$t(a_j) > t(a_i)$ ,和t的最小的定义矛盾, 必定没有方案

所以$t(a_j)\le t(a_i)$

同样从幂次的因子角度考虑

3->2->6->4->5->1 长度6

而6的因子有1,2,3,6

例如 $2=3^2$,$2^t=3^{2t}$,所以2->4->1实际上是上面2的倍数项

例如 $6=3^3$,$6^t=3^{3t}$,所以6->1实际上是上面3的倍数项

所以$a_i^x$如果$x$是$t(a_i)$的因子,那么$t(a_i^x)\equiv \frac{t(a_i)}{x}$

而如果拉长

1
2
3
4

[              ]  [              ]
3->2->6->4->5->1->3->2->6->4->5->1
         |           |           |
         4           2           1

这里有$t(3^{len=4})=3=\frac{1}{2}6=\frac{1}{2}t(3)$

而 这种倍长过程实际就是在求$lcm(t(3),len=4)$

所以显然$t(a^x)=\frac{lcm(x,t(a))}{x}=\frac{t(a)}{\gcd(x,t(a))}$

$t(a_j)=t(a_i^k)=\frac{t(a_i)}{\gcd(k,t(a_i))}$

2和3都是6的因子不太好考虑不是的情况

现在考虑p=11,那么p-1=10,因子有1,2,5,10

1
2
3

      2->4->8->5->10->9->7->3->6->1
pow   1  2  3  4   5  6  7  8  9  10
len   10 5 10  5   2  5 10  5 10  1

注意到1~10每个数字可以都表示成 2的幂次，所以, 它们的链，不过是2多次增长以后，按照幂次跳跃取得的

一个猜想:

长度成倍数，则包含：t(a_i) % t(a_j) =0则$a_i^k\equiv a_j\pmod{p}$

那么p=11也不是个好例子，看看p=13,p-1=12,这样的话长度可能是4和6,而4和6不是倍数关系却gcd不为1

1
2
3
4
5
6

    2->4->8->3->6->12->11->9->5->10->7->1
pow 1  2  3  4  5   6   7  8  9  10 11 12
         [1]        2         3         4 长度4的链
          3         2        [1]        4 长度4的链
      [1]    2      3      4      5     6 长度6的链
       5     4      3      2     [1]    6 长度6的链

虽然有重叠元素，但是互相不包含,

对于oi比赛，那这个时候，已经可以编码了

那么问题来了，数学上如何证明呢？？？？？？

而且这样的方法 因子可能有8e3量级的个数, 在计算 t(a_i)时 时间似乎不够 2e5 * 8e3 * log(8e3,2) ~= 2e10

所以 数学证明 和 效率都有问题

https://codeforces.com/contest/1916

E. Happy Life in University(1s,512mb)

n(3e5)个点,根1的树, 每个点有颜色,求$\max(diff(u,lca(u,v)) * diff(v,lca(u,v)))$

其中$diff(u,v) =$,简单路径u到v上不同颜色的个数

我的思路

有想过dp,但是显然dp[u] =最长向下路径,是不行的因为 向上转移时需要知道是否有对应颜色

如果u,v是最大的方案

• u,v没有祖先关系,那么u,v可以走到其下的任意位置,答案不会更差
• u,v是祖先关系,那么一个向根走,一个向叶子走, 答案不会更差

因此 ans = max(f(叶子,叶子),f(根,叶子))

对于最近同色也是 可以简单的dfs+按照颜色的栈来做, 这样可以O(n)计算出每个点最近同色祖先

想过把树按照dfs序铺平成数组, 这样需要支持一种叫 整线段贡献

1
2
3
4

对于颜色c
  .....in[u]...in[v]...out[v]...out[u]
单点     +1       +1      -1       -1
线段     [   -1    ]     [    +1    ]

这样就变成 对于u,

找[in[u]....childa...] x [in[u]....childb...]

问题是这样支持线段后,如果直接用前缀和就有问题了

https://codeforces.com/contest/1909

F2 - Small Permutation Problem (Hard Version)

问有多少个 1~n的排列$p$满足, 对于所有$a_i \ne -1$时:

• $\mathrm{count}(p_{1\cdots i}\le i) = a_i$

范围

$n\in [1,2\cdot 10^5]$

$a_i \in [-1,n]$

个数$\bmod 998’244’353$

2s

256mb

我的思路

对于F1来说$a_i$是没有$-1$的, 那么$a_i$的变化只有$+0,+1,+2$三种

通过dp[i]=前i个限制满足,且只关心前面位置对于放置[1..i]的放置方案即可AC

而这里感觉要处理的就是,两个相邻非$-1$之间的$a_i \to a_j$的转移

有点想用生成函数,$[x^a]f_{i} =$前i个满足时,且第i个的对应个数为$a$的方案数

在转移的优化上,因为一旦$a \ne -1$,那么生成函数其它的系数全为$0$

所以 可以考虑幂次平移 $g_{i} = \frac{f_{i}}{x^a}$

而对于$a = -1$的找比它小的最后一个非$-1$的a来转换

但转移方程似乎会上到二阶导数,没推出简洁的式子

https://atcoder.jp/contests/abc334

G - Christmas Color Grid 2

h x w 地图上0/1

4邻的1为连通块

求等概率把一个1改成0以后 exp(连通块个数) mod 998244353

h,w 1000

2s

1024mb

我的思路

就是找 去掉点后是否还连通，tarjan的算法

然后写出问题了

https://atcoder.jp/contests/abc333

G - Nearest Fraction

给一个(0,1)之间,不超过18位的小数r

求 一个分母<= N的最接近它的分数，如果有多个则输出最小的

n 1e10

2s

1024mb

我的思路

首先r肯定是通过字符串读取变成 整数/10的幂次

然后可以用 连分数的形式展开它

问题是这样的截断连分数因为分母<= N的限制 似乎直接截断不是最优的，二分最后一个位置的值？

例如样例$0.45, N = 5$

$\displaystyle 0.45=\frac{45}{100}=\frac{9}{20}=0+\frac{1}{\frac{20}{9}}=0+\frac{1}{2+\frac{1}{\frac{9}{2}}}=\frac{9}{20}=0+\frac{1}{\frac{20}{9}}=0+\frac{1}{2+\frac{1}{4+\frac{1}{2}}}$

这里 的 连分数是$[0,2,4,2]$

截断的话会是$\frac{1}{2},\frac{9}{4}$ 之间

而最优是$\frac{2}{5} = [0,2,2]$

所以想法是在会超过的地方 做个除法

然而 比较小数C++精度不够，用分数比较 longlong也会overflow

所以直接换语言，上python, 一次性过了