题目描述

原题地址: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)$,类似地,我们可以推出方程:

阅读全文

题目描述

原题地址:COGS 洛谷

思路

第一问很简单,最长下降子序列问题,第二问的统计方案数有点意思。

DP方程

阅读全文

题目描述

原题地址:COGS BZOJ

思路

合法的n是一个区间,可以分成两次求,二分n的范围。注意有一些关于long long和代码的细节,这个checker还是很好写的

阅读全文

题目描述

原题地址:COGS

思路

本来没有什么想法,搜了一下题解之后发现一个很妙的方法,将字符串正反各读一遍,然后求最长公共子序列的长度,最后再用总长度减一下就可以了

阅读全文

题目描述

题目地址:COGS

这题真是蛇,调一晚上。。码力太弱了qwq

思路

本来以为这跟HAOI2016的食物链一样,但是在WA了一次后注意到食物链计算的是经过某点的路径条数,而本题是经过某边的路径条数。

DP 方程

为了求出经过某一条边的的路径条数,可以这样:

设$f(u,v)$是经过边$u,v$的路径条数,$dp(u)$为从源点到$u$的路径条数,$rdp(v)$为从$v$到终点的路径条数,则有
$f(u,v)=dp(u)\times rdp(v)$
最后的答案就是$\max{f(u,v)} u,v\in G$

为了实现这个操作,我们先正常建图,求出$rdp(u)$,再反向建图,求出$dp(v)$,最后对于每一条边都合并一下答案即可。

阅读全文