模拟赛 - NOI 模拟三&四

2015.12.28 08:41 Mon| 60 visits oi_2016| 2016_竞赛日常| Text

矩阵

一个 n*n 的矩阵,每个方格中可能是 -1 或 1。经过一次变换后,方格里的每个数将会变成变换前与之相邻的 4 个数的积。但有一些状态,变换后的和变换前的是一样的,例如全部是 1 的状态。这种状态称为不变状态。

给定一个已经填了若干数的矩阵,请统计将其余的方格填完后可以得到的不变状态有多少种?(旋转翻转后重合的算多种)

在确定了第一行之后,表格中剩余的数字就都可以确定了。

将 1 看作 0,将 -1 看作 1,我们可以将乘法操作转化为异或操作,表格中每一个数都是第一行中特定的几个数的异或和。这样我们用 O(n^3) 的时间预处理出表格中每一个数由哪些数异或而来,就可以根据已经填好的数列出 O(n) 个方程了。发现最后一行有可能不满足限制条件,所以还需要再列出 O(n) 个方程来限制最后一行的数字。

最后,把所有的方程放在一起高斯消元,答案就是 2^自由元的个数。使用 bitset 优化,就可以通过这道题了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n, m, t[N][N], tot, c[N];
bitset<N> b1[N], b2[N], b[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int gauss()
{
    int re = 0, t = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = t; j <= tot; ++j)
            if (b[j].test(i)) { swap(b[t], b[j]), swap(c[t], c[j]); break; }
        if (!b[t].test(i)) { ++re; continue; }
        for (int j = t + 1; j <= tot; ++j)
            if (b[j].test(i)) { b[j] ^= b[t], c[j] ^= c[t]; }
        ++t;
    }
    while (t <= tot) if (c[t++]) return -1;
    return re;
}

int main()
{
    cin >> n >> m;
    memset(t, -1, sizeof t);
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(), t[x][y] = ((read() + 1) / 2) ^ 1;
    for (int i = 1; i <= n; ++i)
    {
        b2[i].set(i);
        if (t[1][i] != -1) b[++tot] = b2[i], c[tot] = t[1][i];
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            swap(b1[j], b2[j]);
        for (int j = 1; j <= n; ++j)
        {
            b2[j] ^= b1[j] xor b1[j - 1] xor b1[j + 1];
            if (t[i][j] != -1) b[++tot] = b2[j], c[tot] = t[i][j];
        }
    }
    for (int i = 1; i <= n; ++i)
        b[++tot] = b2[i] xor b2[i - 1] xor b2[i + 1] xor b1[i], c[tot] = 0;
    int ans = gauss();
    if (ans == -1) cout << 0 << endl;
    else cout << (1ll << ans) << endl;
    return 0;
}

BZOJ3533 [Sdoi2014]向量集

将向量看作是平面上的点。如果询问的向量的 y 大于 0,那么答案一定出现在询问集合的上凸壳上,否则答案出现在下凸壳上。三分在凸壳上查找答案即可。

现在问题在于如何动态维护一段区间内的凸壳。发现每一次加点都是加到区间的末尾,于是可以考虑用线段树来维护区间内的凸壳。当加点时发现某一个结点表示的一段区间被填满了,就可以将两个儿子节点里的凸壳合并,作为当前结点表示区间内元素的凸壳。由于还没有被加进的点一定不会被询问到,所以这种方式可以保证正确性。每一个结点只会被 O(L) 地更新一次,因此也可以保证时间复杂度为 O(N*log2N)。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 400005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n; char str[5];

struct point
{
    int x, y;
    point() {}
    point(int _x, int _y) : x(_x), y(_y) {}
    bool operator <(const point &p) const
    { return x == p.x ? y < p.y : x < p.x; }
    point operator +(point p) { return point(x + p.x, y + p.y); }
    point operator -(point p) { return point(x - p.x, y - p.y); }
    friend long long dot(point a, point b)
    { return 1ll * a.x * b.x + 1ll * a.y * b.y; } 
    friend long long cross(point a, point b)
    { return 1ll * a.x * b.y - 1ll * a.y * b.x; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

vector<point> hull1[N * 4], hull2[N * 4];

void addpoint(vector<point> &v, point p)
{
    while (v.size() > 1)
    {
        point t = v.back(); v.pop_back();
        if (cross(t - v.back(), p - t) > 0) { v.push_back(t); break; }
    }
    v.push_back(p);
}

void pushup(int pos)
{
    for (int i = 0, j = 0; i < (int)hull1[lson].size(); ++i)
    {
        while (j < (int)hull1[rson].size() && hull1[rson][j] < hull1[lson][i])
            addpoint(hull1[pos], hull1[rson][j]), ++j;
        addpoint(hull1[pos], hull1[lson][i]);
        if (i == (int)hull1[lson].size() - 1)
            while (j < (int)hull1[rson].size())
                addpoint(hull1[pos], hull1[rson][j]), ++j;
    }
    for (int i = 0, j = 0; i < (int)hull2[lson].size(); ++i)
    {
        while (j < (int)hull2[rson].size() && hull2[lson][i] < hull2[rson][j])
            addpoint(hull2[pos], hull2[rson][j]), ++j;
        addpoint(hull2[pos], hull2[lson][i]);
        if (i == (int)hull2[lson].size() - 1)
            while (j < (int)hull2[rson].size())
                addpoint(hull2[pos], hull2[rson][j]), ++j;
    }
}

void insert(int pos, int l, int r, int x, point y)
{
    if (l == r) { hull1[pos].push_back(y), hull2[pos].push_back(y); return; }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(lson, l, mid, x, y);
    else insert(rson, mid + 1, r, x, y);
    if (x == r) pushup(pos);
}

long long getans(vector<point> &v, point p)
{
    int l = 0, r = v.size() - 1;
    long long re = 0x8000000000000000ll;
    while (l <= r)
    {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        long long ans1 = dot(v[lmid], p), ans2 = dot(v[rmid], p);
        re = max(re, max(ans1, ans2));
        if (ans1 < ans2) l = lmid + 1;
        else if (ans1 > ans2) r = rmid - 1;
        else l = lmid + 1, r = rmid - 1;
    }
    return re;
}

long long query(int pos, int l, int r, int x, int y, point z)
{
    if (x <= l && r <= y)
        return getans(z.y >= 0 ? hull2[pos] : hull1[pos], z);
    int mid = (l + r) >> 1;
    if (y <= mid) return query(lson, l, mid, x, y, z);
    if (x > mid) return query(rson, mid + 1, r, x, y, z);
    return max(query(lson, l, mid, x, y, z),
               query(rson, mid + 1, r, x, y, z));
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

long long lastans;
inline int decode(int x)
{ return str[0] == 'E' ? x : x ^ (lastans & 0x7fffffff); }

int main()
{
    scanf("%d%s", &n, str);
    for (int x, y, l, r, tot = 0, i = 1; i <= n; ++i)
    {
        scanf("%s", str + 1);
        if (str[1] == 'A')
            x = decode(read()), y = decode(read()),
            insert(1, 1, n, ++tot, point(x, y));
        else
            x = decode(read()), y = decode(read()),
            l = decode(read()), r = decode(read()),
            printf("%lld\n", lastans = query(1, 1, n, l, r, point(x, y)));
    }
    return 0;
}

BZOJ3711 [PA2014]Druzyny

这题太神了。总体思路是 CDQ 分治,每一次挑分治区间内 c[mid] 最小的 mid 作为中点,可使在这一层分治内的时间复杂度为左右两段子区间的长度的较小值。

首先用线段树预处理出每一个点 i 所在区间向左最远能延伸到哪里,将它们记作新的 d[i]。分治 (l, mid, r) 时,枚举 i = [mid...r],能够更新 i 的元素的范围是 [max(d[i] - 1, l - 1), min(i - c[mid], mid - 1)]。当 i - c[mid] 小于 mid 时,这个范围每一次会右移 1,之后这个范围的右端点就会固定在 mid - 1 这个位置了。枚举 i 的时候左端点也有可能右移,但对于每一个点 i,左端点最多右移一次。

然后,每一次移动左端点,重新算一遍这个范围内最大的元素;每一次移动右端点,用新增加的元素更新之前的最大值。当右端点不再移动之后,可以使用线段树对 d[i] 相同的 i 进行区间更新。

整个算法只需要维护三四个线段树 233。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 1000005
#define TREE 4000005
#define mod 1000000007
#define lson (pos << 1)
#define rson (pos << 1 | 1)
#define zero make_pair(-1, 0)

int n, c[N], d[N];
pair<int, int> f[N], maxc[TREE], maxf[TREE], newf[TREE];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void build(int pos, int l, int r)
{
    if (l == r)
    {
        maxc[pos] = make_pair(c[l], l),
        newf[pos] = make_pair(d[l], l); return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    maxc[pos] = max(maxc[lson], maxc[rson]);
    newf[pos] = min(newf[lson], newf[rson]);
}

pair<int, int> queryc(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return maxc[pos];
    int mid = (l + r) >> 1;
    if (y <= mid) return queryc(lson, l, mid, x, y);
    if (x > mid) return queryc(rson, mid + 1, r, x, y);
    return max(queryc(lson, l, mid, x, y),
               queryc(rson, mid + 1, r, x, y));
}

int queryd(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return newf[pos].first;
    int mid = (l + r) >> 1;
    if (y <= mid) return queryd(lson, l, mid, x, y);
    if (x > mid) return queryd(rson, mid + 1, r, x, y);
    return min(queryd(lson, l, mid, x, y),
               queryd(rson, mid + 1, r, x, y));
}

void update(pair<int, int> &x, pair<int, int> y)
{
    if (x.first == y.first) x.second = (x.second + y.second) % mod;
    else if (x.first < y.first) x = y;
}

void insertf(int pos, int l, int r, int x, pair<int, int> y)
{
    update(maxf[pos], y);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insertf(lson, l, mid, x, y);
    else insertf(rson, mid + 1, r, x, y);
}

pair<int, int> queryf(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return maxf[pos];
    int mid = (l + r) >> 1;
    if (y <= mid) return queryf(lson, l, mid, x, y);
    if (x > mid) return queryf(rson, mid + 1, r, x, y);
    pair<int, int> re = queryf(lson, l, mid, x, y);
    update(re, queryf(rson, mid + 1, r, x, y));
    return re;
}

void changef(int pos, int l, int r, int x, int y, pair<int, int> z)
{
    if (x <= l && r <= y) { update(newf[pos], z); return; }
    int mid = (l + r) >> 1;
    if (x <= mid) changef(lson, l, mid, x, y, z);
    if (y > mid) changef(rson, mid + 1, r, x, y, z);
}

pair<int, int> getf(int pos, int l, int r, int x)
{
    if (l == r) return newf[pos];
    int mid = (l + r) >> 1;
    pair<int, int> re = newf[pos];
    if (x <= mid) update(re, getf(lson, l, mid, x));
    else update(re, getf(rson, mid + 1, r, x));
    return re;
}

void solve(int l, int r)
{
    static pair<int, int> temp;
    if (l > r) return;
    int mid = queryc(1, 1, n, l, r).second;
    solve(l, mid - 1);
    temp = zero;
    for (int i = max(mid, l + c[mid] - 1),
        tl = -1, tr = i - c[mid] - 1; i <= r; ++i)
    {
        if (max(l - 1, d[i] - 1) > tl)
            tl = max(l - 1, d[i] - 1),
            temp = tl <= tr ? queryf(1, 0, n, tl, tr) : zero;
        if (++tr >= mid)
        {
            tr = mid - 1;
            int t = r;
            if (d[i] != d[r])
                t = upper_bound(d + i, d + r, d[i]) - d - 1;
            if (temp.second > 0)
                changef(1, 1, n, i, t, temp);
            i = t;
        }
        else
        {
            if (tl <= tr) update(temp, f[tr]);
            if (temp.second > 0)
                update(f[i], make_pair(temp.first + 1, temp.second));
        }
    }
    temp = getf(1, 1, n, mid);
    update(f[mid], make_pair(temp.first + 1, temp.second));
    insertf(1, 0, n, mid, f[mid]);
    solve(mid + 1, r);
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        c[i] = read(), d[i] = read();
    build(1, 1, n);
    d[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        d[i] = max(d[i - 1], i - d[i] + 1);
        while (i - d[i] + 1 > queryd(1, 1, n, d[i], i)) ++d[i];
    }
    for (int i = 1; i <= n * 4; ++i)
        newf[i] = zero;
    insertf(1, 0, n, 0, f[0] = make_pair(0, 1));
    solve(1, n);
    if (f[n].first == 0) puts("NIE");
    else printf("%d %d\n", f[n].first, f[n].second);
    return 0;
}

出题

简单的斜率优化 DP,我竟然会做。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, m;
int a[N], b[N];
long long sum[N], ans;
vector<pair<long long, long long> > v;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), sum[i] = sum[i - 1] + a[i];
    for (int i = 1; i <= m; ++i)
        b[i] = read();
    for (int i = 1; i <= n; ++i)
    {
        while (v.size() > 1)
        {
            pair<long long, long long> p = v.back(); v.pop_back();
            if ((p.second - v.back().second) * (sum[i] - p.first) <
                (sum[i - 1] - p.second) * (p.first - v.back().first))
                { v.push_back(p); break; }
        }
        v.push_back(make_pair(sum[i], sum[i - 1]));
    }
    for (int i = 1; i <= m; ++i)
    {
        int l = 0, r = v.size() - 2, re = v.size() - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if ((v[mid + 1].second - v[mid].second) * b[i] >
                (v[mid + 1].first - v[mid].first) * b[i - 1])
                re = mid, r = mid - 1;
            else l = mid + 1;
        }
        ans += v[re].first * b[i - 1] - v[re].second * b[i];
    }
    cout << ans + sum[n] * b[m] << endl;
    return 0;
}

BZOJ3935 Rbtree

单纯形啊单纯形。对偶原理之后有初始解,初始解全 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
#include <bits/stdc++.h>
using namespace std;

#define inf 1e99
#define eps 1e-8
#define N 505

struct lin_pro
{
    int n, m;
    double a[N][N], b[N], c[N], v;

    void pivot(int l, int e)
    {
        b[l] /= a[l][e];
        for (int i = 1; i <= n; ++i)
            if (i != e) a[l][i] /= a[l][e];
        a[l][e] = 1 / a[l][e];
        for (int i = 1; i <= m; ++i)
            if (i != l && fabs(a[i][e]) > eps)
            {
                b[i] -= a[i][e] * b[l];
                for (int j = 1; j <= n; ++j)
                    if (j != e) a[i][j] -= a[i][e] * a[l][j];
                a[i][e] = -a[i][e] * a[l][e];
            }
        v += c[e] * b[l];
        for (int i = 1; i <= n; ++i)
            if (i != e) c[i] -= c[e] * a[l][i];
        c[e] = -c[e] * a[l][e];
    }

    double simplex()
    {
        while (true)
        {
            int e = 0;
            for (int i = 1; i <= n; ++i)
                if (c[i] > eps) { e = i; break; }
            if (!e) return v;
            double temp = inf; int l = 0;
            for (int i = 1; i <= m; ++i)
                if (a[i][e] > eps && b[i] / a[i][e] < temp)
                    temp = b[i] / a[i][e], l = i;
            if (temp == inf) return inf;
            pivot(l, e);
        }
    }
} lp;

int n, d, col[N], head[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[1005];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int p, int x, int fa, int val)
{
    if (val > d) return;
    lp.a[x][p] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            dfs(p, edge[i].to, x, val + edge[i].val);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> d;
    lp.n = n + 2, lp.m = n;
    for (int i = 1; i <= n; ++i)
        if ((col[i] = read()) == 0) lp.b[i] = 1;
    int tot = 0;
    for (int i = 1; i <= n; ++i)
        tot += col[i];
    for (int i = 1; i <= n; ++i)
        lp.a[i][n + 1] = 1, lp.a[i][n + 2] = -1;
    lp.c[n + 1] = tot;
    lp.c[n + 2] = -tot;
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    for (int i = 1; i <= n; ++i)
        lp.c[i] = 1, dfs(i, i, 0, 0);
    double ans = lp.simplex();
    if (ans > n) puts("-1");
    else cout << int(ans + 0.1) << endl;
    return 0;
}

BZOJ3434 [Wc2014]时空穿梭

这题也是太神了。

所有点都在同一条直线上,说明在每一个维度上点与点之间间距的比例都是相同的。

令 f(c, l) 表示把 c 个点放在长度为 l 的区间上,并且保持当前的比例无法让 l 更小的方案数。显然这个可以用莫比乌斯反演预处理出来。这样对于每组数据枚举 l,再枚举维度,60 分就拿到了。

对于每一个 l,答案都是一个关于 l 的 n 次多项式。观察发现对于很多的 l,在所有维度 d 上 ⌊m[d] / l⌋ 的值都不会改变,即这个多项式除 f(c, l) 外的系数都不会改变。预处理出 ij*f(c, i) 的前缀和,分块求出多项式的系数,一起乘以乘,这道题就搞完了。

  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
#include <bits/stdc++.h>
using namespace std;

#define mod 10007
#define inf 0x3f3f3f3f

int test, fac[mod], inv[mod];
int f[100005], sum[22][100005][12], xpow[100005][12], n, c, m[22];

int calc(int m, int n)
{
    if (m < n) return 0;
    if (n == 0) return 1;
    if (n == 1) return m;
    return fac[m] * inv[fac[n] * fac[m - n] % mod] % mod;
}

int p[100005], mu[100005], v[100005], tot;

void getmu(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!v[i]) p[++tot] = i, mu[i] = -1;
        for (int j = 1; i * p[j] <= n; ++j)
        {
            v[i * p[j]] = true;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else { mu[i * p[j]] = 0; break; }
        }
    }
}

void play()
{
    fac[0] = 1;
    for (int i = 1; i < mod; ++i)
        fac[i] = fac[i - 1] * i % mod;
    inv[1] = 1;
    for (int i = 2; i < mod; ++i)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    getmu(100000);
    for (int i = 1; xpow[i][0] = 1, i <= 100000; ++i)
        for (int j = 1; j <= 11; ++j)
            xpow[i][j] = 1ll * xpow[i][j - 1] * i % mod;
    for (int c = 1; c <= 20; ++c)
    {
        memset(f, 0, sizeof f);
        for (int i = 1; i <= 100000; ++i)
        {
            int t = calc((i - 1) % mod, c - 2);
            for (int j = 1; j * i <= 100000; ++j)
                f[j * i] = (f[j * i] + t * mu[j]) % mod;                
        }
        for (int i = 1; i <= 100000; ++i)
            for (int j = 0; j <= 11; ++j)
                sum[c][i][j] = (sum[c][i - 1][j] + xpow[i][j] * f[i]) % mod;
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    play();
    while (test--)
    {
        n = read(), c = read();
        int temp = inf;
        for (int i = 1; i <= n; ++i)
            m[i] = read(), temp = min(temp, m[i]);
        if (n == 1) { cout << calc(m[1] % mod, c) << endl; continue; }
        long long ans = 0;
        for (int l = 1, last; l <= temp; l = last + 1)
        {
            last = inf;
            for (int i = 1; i <= n; ++i)
                last = min(last, m[i] / (m[i] / l));
            long long a[15] = {0};
            a[0] = 1;
            for (int i = 1; i <= n; ++i)
            {
                long long t = m[i] / l;
                long long k = -t * (t + 1) / 2 % mod, b = t * m[i] % mod;
                for (int j = i; j; --j)
                    a[j] = k * a[j - 1] % mod + b * a[j] % mod % mod;
                a[0] = b * a[0] % mod;
            }
            for (int i = 0; i <= n; ++i)
                a[i] = (a[i] % mod + mod) % mod;
            for (int i = 0; i <= n; ++i)
                ans = ans + a[i] * (sum[c][last][i] - sum[c][l - 1][i]) % mod;
            ans = (ans % mod + mod) % mod;
        }
        cout << ans << endl;
    }
    return 0;
}