POJ 2167 - Irrelevant Elements

http://poj.org/problem?id=2167

概要

数列 \(a_n\) がある。 長さ \(n\) の数列から、隣接する項の和から新たに長さ \(n-1\) の数列を作ることができる。 このとき足し算は \(\mbox{mod}\ m\) で行う。 これを繰り返して最終的に長さ1の数列を得て、この要素の値を乱数として採用する。

しかしこのとき、最初の数列 \(a_n\) の中で乱数の値に全く影響を及ぼさない要素があるときがある。 そのような要素のインデックスをすべて答える。

制約

• \(1 \le n \le 10 ^ 5\)
• \(2 \le m \le 10 ^ 9\)

解法

最終的に得られる乱数は \(\sum_{i=0} ^ {n-1} {}_{n-1}\mathrm{C}_i a_i\) であるので、 \({}_{n-1}\mathrm{C}_i\) が \(m\) の倍数となるような \(i\) をすべて出力すればよい。

階乗の素因数分解は高速に行えるので、\({}_{n-1}\mathrm{C}_i\) を階乗の形で表現して素因数分解を行い、\(m\) の素因数分解の結果と比較して倍数になっているかどうかを判定する。

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int fact_factor(int n, int p)
 6 {
 7   int ans = 0;
 8   while (n != 0) {
 9     ans += n/p;
10     n /= p;
11   }
12   return ans;
13 }
14 
15 void factorize(vector<pair<int,int> >& fs, int m)
16 {
17   for (int i = 2; i*i <= m; i++) {
18     if (m % i == 0) {
19       int c = 0;
20       while (m % i == 0) {
21         ++c;
22         m /= i;
23       }
24       fs.push_back(make_pair(i, c));
25     }
26   }
27   if (m != 1) {
28     fs.push_back(make_pair(m, 1));
29   }
30 }
31 
32 bool check(const vector<pair<int,int> >& fs, int N, int K)
33 {
34   for (vector<pair<int,int> >::const_iterator it = fs.begin(); it != fs.end(); ++it) {
35     const int p = it->first;
36     const int n = it->second;
37     if (fact_factor(N, p) - fact_factor(K, p) - fact_factor(N-K, p) < n) {
38       return false;
39     }
40   }
41   return true;
42 }
43 
44 int main()
45 {
46   int N, M;
47   scanf("%d %d", &N, &M);
48   vector<pair<int,int> > fs;
49   factorize(fs, M);
50 
51   vector<int> ans;
52   --N;
53   for (int i = 0; i <= N; i++) {
54     if (check(fs, N, i)) {
55       ans.push_back(i+1);
56     }
57   }
58   printf("%lu\n", ans.size());
59   for (vector<int>::const_iterator it = ans.begin(); it != ans.end(); ++it) {
60     if (it != ans.begin()) {
61       putchar(' ');
62     }
63     printf("%d", *it);
64   }
65   putchar('\n');
66   return 0;
67 }