Problem Set.

Table of Contents

  1. Overview
  2. Codeforces 57 C Array
    1. Code
    2. Summary
  3. Codeforces 223 C Partial Sums
    1. Code
  4. Codeforces 296 B Yaroslav and Two Strings
    1. Code

Overview

To improve the ability of solving combinatorics problems (with math, dp, graph theory or others), I wrote this to help record experiences.

Codeforces 57 C Array

Solution

Code

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 1e+5 + 5;
const ll p = 1e+9 + 7;

int n;
ll fac[maxn], inv[maxn], ans;

ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % p;
    base = base * base % p;
    index >>= 1;
  }
  return ret;
}
inline ll C(int nn, int mm) {
  return fac[nn] * inv[mm] % p * inv[nn - mm] % p;
}

int main() {
  scanf("%d", &n);
  fac[0] = inv[0] = fac[1] = inv[1] = 1ll;
  for (int i = 2; i <= n; ++i) {
    fac[i] = fac[i - 1] * (ll)i % p;
    inv[i] = quick_power(fac[i], p - 2);
  }
  for (int i = 1; i <= n; ++i){
    ll tmp = C(n, i) * C(n - 1, i - 1) % p;
    ans = (ans + tmp) % p;
  }
  ans = (ans * 2ll % p - n + p) % p;
  cout << ans << endl;
  return 0;
}

Summary

Begin solving combinatorics problems today. Need to improve the ability of recognize the model behind the problem. At first, I didn’t realize the way of choosing and using numbers, which leads to the failure of solving problem.

Codeforces 223 C Partial Sums

Solution

Code

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll p = 1e+9 + 7;
const int maxn = 2005;
int n, k;
ll inv[maxn], a[maxn], c[maxn], s[maxn];
void init() {
  inv[1] = 1;
  for (int i = 2; i <= 2000; ++i) {
    inv[i] = (-(p/i) + p) * inv[p % i] % p;
  }
}
int main() {
  init();
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];

  if(!k) {
    for(int i = 1; i <= n; ++i) s[i] = a[i];
  } else {
    c[1] = 1;
    for (int i = 2; i <= n; ++i) c[i] = c[i - 1] * (k + i - 2) % p * inv[i - 1] % p;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= i; ++j) s[i] = (s[i] + c[i - j + 1] * a[j] % p) % p;
  }
  for (int i = 1; i <= n; ++i) cout << s[i] << " ";
  cout << endl;
  return 0;
}

Codeforces 296 B Yaroslav and Two Strings

Reversing Problem.

Solution

Code

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
55
56
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e+5 + 5;
const ll mod = 1e+9 + 7;
int n;
ll tot, sle, wle, equ;
char s[maxn], w[maxn];
inline void solve1() {
  for (int i = 1; i <= n; ++i) {
    if (s[i] == '?' && w[i] == '?') sle = sle * 55 % mod;
    else if (s[i] == '?' && w[i] != '?') sle = sle * (w[i] - '0' + 1) % mod;
    else if (s[i] != '?' && w[i] == '?') sle = sle * (10 - (s[i] - '0')) % mod;
    else if (s[i] - '0' > w[i] - '0') {
      sle = 0; break;
    }
  }
}
inline void solve2() {
  for (int i = 1; i <= n; ++i) {
    if (s[i] == '?' && w[i] == '?') wle = wle * 55 % mod;
    else if (s[i] == '?' && w[i] != '?') wle = wle * (10 - (w[i] - '0')) % mod;
    else if (s[i] != '?' && w[i] == '?') wle = wle * (s[i] - '0' + 1) % mod;
    else if (s[i] - '0' < w[i] - '0') {
      wle = 0; break;
    }
  }
}
inline void solve3() {
  for (int i = 1; i <= n; ++i) {
    if (s[i] == '?' && w[i] == '?') equ = equ * 10 % mod;
    else if (s[i] != '?' && w[i] == '?') continue;
    else if (s[i] == '?' && w[i] != '?') continue;
    else if (s[i] - '0' != w[i] - '0')  {
      equ = 0; break;
    }
  }
}
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1); scanf("%s", w + 1);
  tot = 1;
  for (int i = 1; i <= n; ++i) {
    if (s[i] == '?') tot = tot * 10ll % mod;
    if (w[i] == '?') tot = tot * 10ll % mod;
  }
  sle = 1; wle = 1; equ = 1;
  solve1(); solve2(); solve3();
  cout << (tot - sle - wle + equ + mod) % mod << endl;
  return 0;
}