UOJ Logo NaCl的博客

博客

puts("hello, 2021")

2020-12-31 13:17:53 By NaCl

这个 OJ 的降生也已满三年。

虽万难君未死也,唯一路尔而行之。

只用等比数列求和过掉 #115

2020-12-20 00:32:56 By NaCl

分治题解见此处

显然,若 $a\mod b=c$,则 $ah\mod bh=ch$。

因此先以 $(a-1)m$ 为模数作快速幂,再除以 $(a-1)$ 即可。

#include <stdio.h>
#include <stdlib.h>

int power_mod(int base, long long int exp, int mod)
{
    long long int result = 1, b2 = base;
    while (exp) {
        if (1 & exp) result = result * b2 % mod;
        b2 = b2 * b2 % mod;
        exp >>= 1;
    }
    return (int)result;
}

int main()
{
    int a, m, m1;
    long long int k;
    scanf("%d%lld%d", &a, &k, &m);
    m1 = m * (a - 1);
    printf("%d\n",
        (m - 1 + (m1 - 1 + power_mod(a, 1 + k, m1)) % m1 / (a - 1)) % m);
    return 0;
}

祝愿++

2020-12-09 22:58:23 By NaCl

原文在此

高三选手,文化课加油,请一如既往。

高二选手,再接再厉,请走下去

高一选手,欢迎来到 OI,请坚持。

对于高二选手

请看这里

题解:#373. 赤壁怀古

2020-12-02 21:00:19 By NaCl
不保证最优,若有更优解法请回复告知。

数位动规。

必须承认本题出得不好(我太菜了),因为「子树有序」这条件实在不优雅。

将 $n$ 节点、子树有序的有根树转化为长度为 $2(n-1)$ 的括号序列,问题便相当显豁了。

会了吧?

——

———

————

———

——

设状态 $s_{i,j}$ 代表括号序列的前 $i$ 位、左括号比右括号多 $j$ 个的情况数。当 $j\gt0$ 时,$s_{i,j}$ 可以转移到 $s_{i+1,j-1}$;当 $j\lt k-1$ 时,$s_{i,j}$ 可以转移到 $s_{i+1,j+1}$。

初始条件为 $s_{0,0}=1$,答案为 $s_{2(n-1),0}$,效率为 $\Theta(nk)$。

由于是大水题,代码非常好写,就不放标程了。

——故国神游,多情应笑我,早生华发。

各代学弟学妹找我啊

2020-11-19 11:21:35 By NaCl

本人,二代阁员,也基大学新生。

不太了解我离开后 LFYZOI 现状,故希望诸君来找我~

鄙 QQ:1362432220

鄙 邮箱:yaosite@139.com

鄙 博客:http://cn-0xis.gitee.io

请叫我「0xis」或「物灵」,OJ 改不了名所以帐号才是 NaCl。

NaCl Avatar