DL24袁小迪 第一次七校模拟题解

作业

Day1

T1 Count

题目描述

给定$n$，求合法的$(x_1, x_2, ..., x_{2m})$组数，对$998244353$取模。
一组$x$是合法的，当且仅当：
1. $\forall x \in [1, 2m], x_i \in N^+, x_i | n.$
2. $\Pi_{i = 1}^{2m} x_i \leq n^m.$

数据范围：

1. $17\%: n \leq 20, m = 2$
2. $28\%: n \leq 100, m \leq 3$
3. $55\%: n \leq 10^9, m \leq 100$

题解

首先所有的$x_i$都是n的因数，总的$x_i$种数不会超过$\sqrt n$.

所有的组$x$可以分为三类：乘积等于$n^m$，乘积小于$n^m$，乘积大于$n^m$.

乘积小于$n^m$的组和乘积大于$n^m$的组是一一对应的，总的组数是可求的，那么只需求出乘积恰好等于$n^m$的组的个数即可。

将n分为多个质数相乘的形式，对于每个质因数，可以知道$n^m$中这个质数的指数，求出2*m个数相加等于这个指数的方案数即可。

T2 Delete

题目描述

有一个1~n的排列，每次可以从中删除一个最长上升子序列或最长下降子序列，请输出一种方案，在500次以内将序列删完。

题解

直接每次nlogn找最长上升子序列或最长下降子序列，然后模拟删除即可……
甚至随便找点东西删（如lzlj同学的做法）都可以……
什么题啊……

T3 Floor

题目描述

求 $\lfloor (\frac{\sqrt 5 + 1}{2})^n \rfloor \mod p$的值。

数据范围：

$n \leq 10^{18}, p \leq 998244353$

题解

这个数是黄金分割率，也就是方程$x^2-x-1=0$的解，所以
$x^2=x + 1$,
那么$x^3 = x^2*x = (x+1)*x = x^2 + x = 2*x + 1$,
$x^4 = 3^x + 2$,
$x^5 = 5^x + 3$...

所以 $x^n = fib[n]*x + fib[n - 1]$

再找规律可以发现，$\lfloor fib[n]*x \rfloor \approx fib[n + 1]$，在n为奇数的时候恰好相等，n为偶数的时候右侧式子要减1。

矩阵快速幂求斐波那契即可。

Day2

T1 Permutation

题目描述

给出$n$和一个$n*n$的矩阵$f[i][j]$，求一个 $1~n$ 的排列x[i]，满足$\forall 1 \le i \neq j \le n, i, j \in N^+$，有$f[i][j] = min(x[i], x[j])$。

数据范围： $n \le 2000$

题解

如果矩阵合法，那么最小的那个数字（即数字1）在矩阵f中一定会呈现一个“十字形”，因为它和所有其他数字比较，都是它更小。删除这个十字后，原先第二小的数，就是剩余的当中最小的数，也符合这个规律。

最后必然出现下面这样的一个矩阵：

0 n
n 0

剩下没填的两位（就是矩阵中涉及的两位）一个是$n - 1$, 一个是$n$。

所以要么-1，要么解的个数是2……

T2 String

暴力
居然
能过
不想
说啥

T3 Number

题目描述

给出一个十进制数$n$和一个数$m$，求满足以下条件的数的个数：
1. 不含前导0；
2. 各位数字颠倒顺序后可以变成n；
3. 是$m$的倍数。

首先，思路肯定是……状压DP！

然鹅怎么状压呢？

根据我荒废近两个小时的思考，可以想象成一个每一位位权不同的多进制数，一共有10位，代表0~9的每个数字，每一位最大值就是n中这个数字出现的次数。这个数可以表示一个数中各个数字出现的次数情况。

例如，n中一共出现了1个“0”，2个“1”，1个“2”，那么要用到的状态有：

000, 001, 010, 011, 020, 021, 100, 101, 110, 111, 120, 121

对应的十进制数分别为0~11。

共2*3*2 = 12种状态。

那么怎么转移呢？

50分的做法是枚举填数的位置i、填的数字j、状态、模m的值。

然而正解根本不需要枚举填数位置，只需默认是最高位即可。

核心代码：

    dp[0][0] = 1;
    for(int i = 1; i < ri[0]; i++)
        for(int j = 0; j <= 9; j++)
            if(getnum(i, j))
                g[i] = g[i - ri[j + 1]] + 1;
    for(int i = 0; i < ri[0]; i++)
        for(int j = (i == ri[0] - 1); j <= 9; j++)
            if(getnum(i, j))
                for(int k = 0; k < m; k++)
                    dp[i][k] = (dp[i][k] + dp[i - ri[j + 1]][((k - wei[g[i]]*j)%m + m)%m]) % P;