题目描述

原题地址:Luogu

一句话题意:维护一个毒瘤可持久化的数组,有单点查询,单点修改的操作

阅读全文

原题描述

题目地址:Luogu

一句话题意,有一个图,每个点都有非负点权,求从一个点开始到达若干源点的最大点权和

阅读全文

题目描述

原题地址:洛谷

由于某些原因,我不想在COGS上刷题了,于是转战洛谷。

用此题练习一下倍增LCA。

阅读全文

题目描述

原题地址:COGS

题目是在济南集训时候的比赛题

题意:求$\sum^n_ {i = 1}\sum_{j=1}^m\gcd(i,j)\mod998244353$

阅读全文

[COGS 1517] 放国王

题目描述

原题地址:COGS

思路

对于此题,先考虑一个弱化版的题目:

  • 在$n\times n$的棋盘上放国王,有多少种方法?

阅读全文

[COGS 1516] 棋盘上的车

题目描述

原题地址:COGS

思路一

乘法原理水过,计算$n!$即可,复杂度$O(n)$

思路二

DP方程

每次放置一枚棋子,一行一行放,可以用一个二进制数表示状态,如$(0010011)_2$表示第一、二、五列已放棋子。

设$f(n)$是放置$n$枚棋子的方案数,可以知道,$f((0010011)_2)=f((0000011)_2)+f((0010001)_2)+f((0010010)_2)$,类似地,我们可以推出方程:

阅读全文