noip模拟47

 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 10000010;

template<typename LDXIN>
LDXIN read() {
  LDXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

long long prime[maxn], tot;
long long l, r, k;
bool vis[maxn];

void s1(long long l, long long r) {
  long long ans = 0;
  For(i, l, r) {
    ans ^= i;
  }
  cout << ans << endl;
}

bool viS[maxn];
int main() {
  l = read<long long>();
  r = read<long long>();
  k = read<long long>();
  k = min(k, (long long)sqrt(r));
  vis[1] = 1;
  if (k == 1) {
    s1(l, r);
    return 0;
  }
  for (long long i = 2; i <= k;i++) {
    if (!vis[i])
      prime[++tot] = i;
    for (long long j = 1; j <= tot && prime[j] <= k && i * prime[j] <= k; j++) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  for (int i = 1; i <= tot; i++) {
    long long stt = max(2 * prime[i], l) / prime[i];
    if (stt * prime[i] < l) stt++;
    while (prime[i] * stt <= r) {
      viS[prime[i] * stt - l] = 1;
      stt++;
    }
  }
  long long ans = 0;
  for (long long i = l; i <= r; i++) {
    
    if (viS[i - l] != 1) {
      ans ^= i;
    }
  }
  cout << ans << endl;
  return 0;
}

 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 1000100;
const long long mod = 1e9 + 7;

template<typename LDXIN>
LDXIN read() {
  LDXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

long long n, m, k;
long long seq[maxn], dp[maxn];

struct PNT {
  long long id, val;
  friend bool operator< (PNT a, PNT b) {
    return a.val > b.val;
  }
};

int main() {
  n = read<long long>();
  m = read<long long>();
  k = read<long long>();
  For(i, 1, n) {
    seq[i] = read<long long>();
  }
  dp[seq[1]] = 1;
  long long sum = 1, tmp = 0;
  For(i, 2, n) {
    tmp = dp[seq[i]] % mod;
    
    dp[seq[i]] = sum + 1;
    dp[seq[i]] %= mod;
    
    sum = (dp[seq[i]] % mod - tmp % mod + mod + sum) % mod;
    sum %= mod;
  }
  priority_queue<PNT> pq;
  For(i, 1, k) {
    pq.push((PNT){i, dp[i]});
  }
  For(i, n + 1, m + n) {
    long long minVal = pq.top().val, minid = pq.top().id;
    pq.pop();
    seq[i] = minid;
    
    tmp = minVal;
    tmp %= mod;
    
    dp[seq[i]] = sum + 1;
    // cout << dp[seq[i]] << endl;
    dp[seq[i]] %= mod;
    
    sum = (dp[seq[i]] % mod - tmp % mod + mod + sum) % mod;    
    sum %= mod;
    
    pq.push((PNT){minid, dp[seq[i]]});
  }
  cout << sum % mod << endl;
  return 0;
}

  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
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 10001100;
const long long mod = 1e9 + 7;

template<typename LDXIN>
LDXIN read() {
  LDXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

// #define DEBUG 1
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  inline char gc() {
#if DEBUG
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }
  inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }
  template <class T>
  inline void read(T &x) {
    register double tmp = 1;
    register bool sign = 0;
    x = 0;
    register char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') sign = 1;
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); isdigit(ch); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }
  inline void read(char *s) {
    register char ch = gc();
    for (; blank(ch); ch = gc())
      ;
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }
  inline void read(char &c) {
    for (c = gc(); blank(c); c = gc())
      ;
  }
  inline void push(const char &c) {
#if DEBUG
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }
  template <class T>
  inline void write(T x) {
    if (x < 0) x = -x, push('-');
    static T sta[35];
    T top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
  }
  template <class T>
  inline void write(T x, char lastChar) {
    write(x), push(lastChar);
  }
} io;



long long n, m, k;
int seq[maxn];
struct DP {
  int val, lst = 0;
  friend bool operator< (DP a, DP b) {
    return a.lst < b.lst;
  }
} dp[maxn];

class MTX {
public:
  struct matrix {
    int a[105][105];
  } ans, base;
  int m;
  void init(int k) {
    m = k + 1;
    For(i, 1, k) {
      ans.a[i][1] = dp[i].val;
    }
    ans.a[k + 1][1] = 1;
    For(i, 1, k - 1) {
      base.a[i][i + 1] = 1;
    }
    For(i, 1, k + 1) {
      base.a[k][i] = 1;
    }
    base.a[k + 1][k + 1] = 1;
  }
  matrix calc(matrix a, matrix b) {
    matrix c;
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= m; j++) {
        c.a[i][j] = 0;
      }
    }
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= m; k++) {
          c.a[i][j] = (c.a[i][j] + 1ll * b.a[i][k] * a.a[k][j]) % mod;
        }
      }
    }
    return c;
  }
  
  void qpow(int power) {
    while (power) {
      if (power & 1) {
        ans = calc(ans, base);
      }
      base = calc(base, base);
      power >>= 1;
    }
  }
} wdnmd;


int32_t main() {
  io.read<long long>(n);
  io.read<long long>(m);
  io.read<long long>(k);
  For(i, 1, n) {
    io.read<int>(seq[i]);
    dp[seq[i]].lst = i;
  }
  dp[seq[1]].val = 1;
  long long sum = 1, tmp = 0;
  For(i, 2, n) {
    tmp = dp[seq[i]].val;
    dp[seq[i]].val = sum + 1;
    dp[seq[i]].val %= mod;
    sum = (dp[seq[i]].val - tmp + sum + mod) % mod;
  }
  sum = 0;
  sort(dp + 1, dp + 1 + k);
  wdnmd.init(k);

  wdnmd.qpow(m);
  For(i, 1, k) {
    sum += wdnmd.ans.a[i][1];
  }
  cout << sum % mod << endl;
  return 0;
}