20普转提day2 题解

发表于 更新于 分类于

马上联赛了，把陈年老题改一下，试图找点自信?

感觉沈睿出的题还是很有技术含量的，只是我不会做就是了。

比赛地址

A 串

感觉直接大力讨论就可以了，因为情况不是很多。

可能是太懒了，这题都不会。

B 数

好像洛谷月赛有一道类似的题。

把数重小到大排序，然后\(f[i]\)表示前\(i\)个数能凑出的最大的数。

即\(f[i]+1\)不能被凑出。

如果\(f[i-1]+1<a[i]\)，\(f[i-1]+1\)即不能被凑出，因为后面的数已经不可能被选。

否则，\(f[i-1]+a[i]\)都可以被凑出，则\(1+a[i],2+a[i],\dots f[i-1]+a[i]\)可以被凑出。

C 图

基础状压都不会...

\(f[i]\)表示子图最小去几条边变成DAG，因为DAG一定有一个度数为\(0\)的点，所以枚举这个点。

从\(f[i\oplus 2^j]\)去掉子图中连向它的边转移过来。

D 睿爸三角

杨辉三角第\(i\) 行，第\(j\)列的值等于\(\binom{i-1}{j-1}\)

即求每一行多少个\(m\)满足\(\binom{n}{m}\bmod 7\neq 0\)

根据Lucas定理\(\binom{n}{m}\%7=\binom{n/7}{m/7}\binom{n\% 7}{m\% 7}\%7\)

即相当于七进制下每一位的组合数的乘积

因为\(7\)是质数，所以只需要没有\(\binom{n}{m}=0\)即可满足条件

即\(m\leq n\)

每一位都有\(bit(n)+1\)种填法。

问题转化为，\(0\)到\(n-1\)所有数在七进制下每一位加一的乘积和。

因为乘法有分配律，就是\(a\times b+a\times c=a\times(b+c)\)

可以数位\(dp\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int N = 40, MOD = 1e9 + 7;
int f[N][2], a[N], cnt;
long long n;

int dfs(int x, int less) {
    if (f[x][less] != -1) return f[x][less];
    if (x == 0) return 1;
    f[x][less] = 0;
    int mx = less ? 6 : a[x];
    for (int i = 0; i <= mx; i++) f[x][less] = (f[x][less] + (i + 1) * 1ll * dfs(x - 1, less || (i < a[x])) % MOD) % MOD;
    return f[x][less];
}

int main() {
    memset(f, -1, sizeof f);
    cin >> n;
    n--;
    while (n) a[++cnt] = n % 7, n /= 7;
    cout << dfs(cnt, 0) << endl;
    return 0;
}