https://atcoder.jp/contests/abc154/tasks
E - Almost Everywhere Zero
- 1≤N<10100
- 1≤K≤3
题意：找到 1 到 N 中在十进制下有 k 个非零位的数的个数。
记忆化dfs
深搜状态 (第 i 位，有 k 个非零位，是否0到9随便选)，状态不多。
分类比较细，要考虑当前位是否可以随便选，还是有上限。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const ll mod = 1000000007;
char s[maxn]; int n;
int k;
int ena;
ll dp[110][4][2];
ll dfs(int dep, int k) {
if (n - dep + 1 < k)return 0;
if (dep == n) {
if (k == 0) {
return 1;
}
else {
if (ena)return 9;
else return s[n] - '0';
}
}
if (k == 0)return 1;
if (dp[dep][k][ena] != -1)return dp[dep][k][ena];
ll res = 0;
if (ena) {
res = 9*dfs(dep + 1, k - 1) % mod;
res = (res + dfs(dep + 1, k)) % mod;
}
else {
if (s[dep] - '0' > 0) {
ena = 1;
res = (s[dep] - '0' - 1)*dfs(dep + 1, k - 1) % mod;
res = (res + dfs(dep + 1, k)) % mod;
ena = 0;
res = (res + dfs(dep + 1, k - 1)) % mod;
}
else {
res = dfs(dep + 1, k) % mod;
}
}
return dp[dep][k][ena] = res;
}
int main() {
scanf("%s", s + 1);
cin >> k;
n = (int)strlen(s + 1);
memset(dp, -1, sizeof(dp));
ena = 0;
cout << dfs(1, k) << endl;
return 0;
};
|
F - Many Many Paths
- 1≤r1≤r2≤106
- 1≤c1≤c2≤106
题意：网格上求出从左上角 (0,0) 到每点的路径数，再给定一个矩形，求矩形里所有点的路径数之和。
数论
并没有做出来，看的题解。
求出每点的路径数 f(i,j) 后打表或者推导发现
f(i,j)=f(i−1,0)+f(i−1,1)+f(i−1,2)+⋯+f(i−1,j)=k=0∑jf(i−1,k)
看到矩阵就变成四个前缀和的加减，所以现在要求二维的前缀和。
由以上的式子得到每一行的和 ∑k=0jf(i,k)=f(i+1,j)
所以二维的和 O(n2) 变成了 O(n).
接下来要 O(1) 求 f(i,j)，显然是要把上面的递推式解出来，然而我并不会，看到题解里也只是直接给出了结论：f(i,j)=i!⋅j!(i+j)!
预处理出阶乘和阶乘逆元即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const ll mod = 1000000007;
ll fact[maxn], inv[maxn];
ll power(ll a, int x) {
ll ans = 1;
while (x) {
if (x & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
x >>= 1;
}
return ans;
}
void init() {
fact[0] = 1ll;
for (int i = 1; i < maxn; i++) {
fact[i] = fact[i - 1] * i %mod;
}
inv[maxn - 1] = power(fact[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}
ll f(int i, int j) {
return fact[i + j] * inv[i] % mod*inv[j] % mod;
}
ll cal(int i, int j) {
ll res = 0;
for (int k = 1; k <= i + 1; k++)
res = (res + f(k, j)) % mod;
return res;
}
int r1, c1, r2, c2;
int main() {
cin >> r1 >> c1 >> r2 >> c2;
init();
ll ans = (cal(r2, c2) + cal(r1 - 1, c1 - 1)) % mod;
ans = (ans - cal(r1 - 1, c2) + mod - cal(r2, c1 - 1) + mod) % mod;
cout << ans << endl;
return 0;
};
|
