| 30 | } |
| 31 | |
| 32 | void testMod() { |
| 33 | for (int it = 0; it < 10000; it++) { |
| 34 | int K = rng() % 20 + 1, |
| 35 | S = rng() % 1000 + 1; |
| 36 | |
| 37 | int k = rng() % K + 1; |
| 38 | vector<Mod> init(k); |
| 39 | rep(i,0,k) init[i] = (int)(rng() % (2*S)) - S; |
| 40 | |
| 41 | vector<Mod> c(k); |
| 42 | rep(i,0,k) c[i] = (int)(rng() % (2*S)) - S; |
| 43 | rep(i,0,k) { |
| 44 | Mod cur = 0; |
| 45 | rep(j,0,k) { |
| 46 | cur = cur + init[(int)init.size()-1 - j] * c[j]; |
| 47 | } |
| 48 | init.push_back(cur); |
| 49 | } |
| 50 | |
| 51 | vector<Mod> res = berlekamp_massey<Mod>(init); |
| 52 | assert(res.size() <= k); |
| 53 | for (int i = k; i < init.size(); i++) { |
| 54 | Mod cur = 0; |
| 55 | rep(j,0,res.size()) { |
| 56 | cur = cur + init[i-1 - j] * res[j]; |
| 57 | } |
| 58 | assert_equal(init[i], cur, true); |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | void testDouble() { |
| 64 | for (int it = 0; it < 10000; it++) { |
no test coverage detected