orz jklover

problem1

1 2	给定n,m，要求选出2m个数，要求每个数都是n的约数，而且所有数的乘积<=n^m，问方案数，答案对998244353取模。 n <= 1e9, m <= 200

考虑对称性，所有数的乘积$\le n^m$和乘积$\ge n^m$方案数显然相等，重的只有$=n^m$的情况，设此时的方案数为$g$，答案就为$\frac{\sigma(n)^{2m}+g}{2}$。

问题来到怎么求取等方案数的问题，我们将每一个质数拉出来分开看（$n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_x^{k_x}$），可以发现，这$2m$个数对于$p_1$来说：
$$
\forall i,cnt_i \le k_1 \\
\sum cnt_i = k_1m
$$
这个东西完全可以$dp$，然后将贡献全部乘到一起，就做完了。

复杂度：$x \cdot m + \sqrt n$，（$x$是$n$的质因数个数）。

problem2

欧拉计划638。

一个坐标轴，从原点出发走向$(a,b)$，每次只能向上或向右走，每条路径的权值定义为：$k^s$，$s$是路径下方与$x$围成的面积，答案对$10^9+7$取模。

首先考虑暴力$dp$，我们考虑如何转移到$f(i,j)$，如果我们考虑计算与$x$轴所平行的线所包含的面积，那么式子一定是：
$$
f(i,j) = f(i - 1,j)+f(i,j-1)\cdot k^i
$$
那么O(n^2)的暴力就有了。

我们重新审视这个式子，这个面积$s$也可以看作路径右边的面积，那么这个式子也可以写成：
$$
f(i,j) = f(i-1, j)\cdot k^j+f(i,j-1)
$$
这两个式子中的$f$函数所代表的意义是完全等价的我们可以联立这两个方程，就可以得到：
$$
f(i-1,j) = \frac{k^i-1}{k^j-1}\cdot f(i,j-1) \\
f(i,j) = \frac{k^{i+1}-1}{k^j-1}
$$
之后递归下去，直到得到答案。

problem3

题目坐标

很基础的一个完全背包，很好想，但当时脑子短路了，死磕网络流无果，注意赋初值。

贴个代码

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 2.5e7 + 5;
int n;
struct Node{
    int x[4];
}a, b;
LL f[N];
int main()
{
    read(n);
    read(a.x[1], a.x[2], a.x[3]);
    read(b.x[1], b.x[2], b.x[3]);
    for(int j = 1;j <= 3;j ++)
        for(int i = a.x[j];i <= n;i ++)
            f[i] = max(f[i], f[i - a.x[j]] + b.x[j] - a.x[j]);
    n = n + f[n];
    memset(f, 0, sizeof(f));
    for(int j = 1;j <= 3;j ++)
        for(int i = b.x[j];i <= n;i ++)
            f[i] = max(f[i], f[i - b.x[j]] + a.x[j] - b.x[j]);
    write(f[n] + n);
    return 0;
}

problem4

【TJOI2019】唱、跳、rap和篮球

problem5

令一个排列中的前缀$gcd$中不同种类的数的个数为$f$，求$n$的排列中最大的$f$，以及有多少种排列等于$f$，对$998244353$取模。

problem6

有一个长为$n$的数列$a_n$，每次操作将序列第一个数加入新数列的队首或队尾，令新数列中最长上升子序列长度为$len$，求最大化的$len$，以及有多少种不同的构造方案的最长上升子序列长度为$len$。

$n \le 10^6$

大水题。

首先考虑解决第一个问，我们任意来看一组新序列。

1	1, x, 2, x, 3, x, x, 4, x, 5, 6

为了使结论更清晰，本人将序列中不贡献答案的数用$x$隐去了。

我们设$3$是这些有贡献的数中在原序列的编号最小的数，则$4,5,6,1,2$的编号一定大于$3$，而如果令一个数在原序列中的编号为$id(x)$的话，一定有$id(2)<id(1)$，$id(4)<id(5)<id(6)$，那么等于是在原数列求出一个最长上升子序列和一个最长下降子序列，然后将他们拼在一起，令$f(x)$为原数列以$x$为开头的最长上升子序列的长度，$g(x)$则为最长下降子序列的长度，第一问答案就为$\max{f(x)+g(x)-1}$，复杂度用线段树可以做到$n\log n$（常数危险）。

考虑第二问，我们发现第二问其实是在第一问的基础上考虑其他数的去处，但是我们并不关心其他数的去处，所以每找到一个第一问的答案就会贡献一个$2^{n-len}$（第一个数没法算两次），

注意：每个起点所拥有的最长上升子序列的个数可能不唯一，所以最后的答案应该是：$\sum cnt(f(x))\cdot cnt(g(x)) \cdot 2^{n - f(x)-g(x)}$。

problem7

problem8

[NOI2020] 美食家

Luckyleaves's Blog

暑假数学杂题选讲