【POJ-1007】DNA Sorting【树状数组求逆序对】

【POJ-1007】DNA Sorting【树状数组求逆序对】

问题链接:https://vjudge.net/problem/POJ-1007

Solution:

使用树状数组求解逆序对,倒序遍历序列,树状数组记录到遍历当前位置出现的所有元素各自的数量【我们将’A’通过’A’ – ‘A’ + 2映射到2,其余字符都是CH – ‘A’ + 2】,对于每个序列中的元素,我们先查询遍历到当前位置出现过多少比它小的元素,每一个计数将代表有一个逆序对,之后将树状数组中当前元素的计数加1.

这道题要求对所有字符串进行逆序对数量从小到大排序,之后输出,使用结构体存放string和计数,并使用计数来排序就好了。

时间复杂度\(O(mnlogn)\).

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int LIM = 30;
int bitree[LIM];

void update(int pos) {
    for (; pos < LIM; pos += pos & (-pos))
        bitree[pos]++;
}

int query(int pos) {
    int ret = 0;
    for (; pos > 0; pos -= pos & (-pos))
        ret += bitree[pos];
    return ret;
}

struct Node {
    string str;
    int cnt;
    bool operator < (const Node &n) const {
        return cnt < n.cnt;
    }
};
vector<Node> dat;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, m;
    Node tmp;
    while (cin >> n >> m) {
        dat.clear();
        for (int i = 0; i < m; i++) {
            cin >> tmp.str;
            tmp.cnt = 0;
            memset(bitree, 0, sizeof bitree);
            for (int j = n - 1; j >= 0; j--) {
                tmp.cnt += query(tmp.str[j] - 'A' + 1);
                // cout << query(tmp.str[j] - 'A' + 1) << endl;
                update(tmp.str[j] - 'A' + 2);
            }
            dat.push_back(tmp);
        }
        sort(dat.begin(), dat.end());
        for (int i = 0; i < m; i++) {
            cout << dat[i].str << '\n';
            // cout << dat[i].cnt << '\n';
        }
    }
    return 0;
}

 

【CodeForces-258A】Little Elephant and Bits【贪心】

【CodeForces-258A】Little Elephant and Bits【贪心】

问题十分简单,给出一个二进制表示的数,要求去除任意一位后,能够取得的最大值,我们使用字符串来操作,因为相同长度下,较大的数值其字典序一定较大【如果长度不一样则不一定满足,需要注意】,在一般情况下,我们只能够删去一个0或者一个1,如果删去0,则删去从左边开始的第一个0会得到所有删去0的结果的最大值,因为它让其右边的所有位数尽可能的向高位靠拢;类似的,如果删去1,则从最右边开始的第一个1删去,可得到所有删去1的结果中最大的值,之后比较这两个值就可以知道是删除0还是删除1的方案得到的数更大。对于特殊情况【全是0或全是1】,需要加一些特殊处理,让最后生成的字符串长度为n【即出现没有删减的情况】,我们检测到删0或删1方案得到的数没有删减时,就可以确认另一种删的方案一定成功删除了,故直接输出另一种方案即可。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin >> str;
    int n = str.size();
    string tmp = "", a, b;
    bool flag = true;
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (flag && str[i] == '0') {
            flag = false;
            continue;
        }
        if (str[i] == '1') pos = i;
        tmp += str[i];
    }
    a = tmp;
    tmp = "";
    for (int i = 0; i < n; i++) {
        if (i == pos && str[i] == '1') continue;
        tmp += str[i];
    }
    b = tmp;
    if (b.size() == n || a.size() != n && a > b)
        cout << a << "\n";
    else
        cout << b << "\n";
    return 0;
}

 

【CodeForces-1029D】Concatenated Multiples

【CodeForces-1029D】Concatenated Multiples

问题链接:http://codeforces.com/problemset/problem/1029/D

Solution:

原来自己没有解决,参照了别人写的题解:http://codeforces.com/blog/entry/61439

首先分析组合后的数:\(a_i * 10^{len_j} + a_j\),这个数如果要被k整除,则必要加号两侧各自被k除后的余数都是0或者相加为k,接下来就是关键的处理步骤了。

如果我们暴力每个i、j,复杂度将是\(O(n^2)\)的,根据这道题的数据范围,规模会达到4e10,所以我们不能采用暴力来解决。参照上边链接内的题解,给出了一种方案,因为我们需要的只是在确定长度时等于0(当\(a_i * 10^{len_j} % k = 0\)时 )或等于\(k – a_i * 10^{len_j} % k\)(当\(a_i * 10^{len_j} % k \neq 0\)时)的\(a_j % k\)的数量,那么为每一种a[i]长度开一个vector,其中存储一下该长度的a[i]对k取模后的值,接着在这里使用它来作为a[j],排序后,可以使用二分搜索来确定索引上下界,索引上界减去索引下界就是数量,之后再判断一下是否包含的当前枚举的a[i]自身就好【如果包含,要将ans–】

根据这个设计,我写的代码是这样:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, k;
    cin >> n >> k;
    table[0] = 1;
    for (int i = 1; i < LENGTH; i++)
        table[i] = table[i - 1] * 10 % k;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        LL tmp = data[i];
        digits[i] = 0;
        while (tmp) {
            tmp /= 10, digits[i]++;
        }
        remain[digits[i]].push_back(data[i] % k);
    }
    for (int i = 0; i < LENGTH; i++)
        sort(remain[i].begin(), remain[i].end());
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < LENGTH; j++) {
            LL rem = data[i] * table[j] % k;
            vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
            vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
            ans += r - l;
            if (j == digits[i] && (rem ? k - rem : 0) == data[i] % k) ans--;
        }
    }
    cout << ans << "\n";
    return 0;
}

rem ? k – rem : 0这个写起来太麻烦了,按照题解的做法,可以改成:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, k;
    cin >> n >> k;
    table[0] = 1;
    for (int i = 1; i < LENGTH; i++)
        table[i] = table[i - 1] * 10 % k;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        LL tmp = data[i];
        digits[i] = 0;
        while (tmp) {
            tmp /= 10, digits[i]++;
        }
        remain[digits[i]].push_back(data[i] % k);
    }
    for (int i = 0; i < LENGTH; i++)
        sort(remain[i].begin(), remain[i].end());
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < LENGTH; j++) {
            LL rem = data[i] * table[j] % k;
            vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
            vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
            ans += r - l;
            if (j == digits[i] && (rem + data[i] % k) % k == 0) ans--;
        }
    }
    cout << ans << "\n";
    return 0;
}

 

【CodeForces-807C】Success Rate【二分】

【CodeForces-807C】Success Rate【二分】

Solution:

一开始按照x *q 与 y * p比较来做的,小于就x++,y++,大于就只y++,结果TLE。然后就按照最初想的,最后结果一定有x’ = kq,且y’ = kp,需要有x’ >= x,y’ >= y,枚举k试了一下,结果发现有问题,样例的3 10 1 2当k取5的时候上面不等式就已经满足了,但是这个k = 5是有问题的,发现y的增量需要保证大于等于x的增量,接着发现增量一做差就是没有通过的数量的增量,那么索性先求出y – x以及p – q,即没有通过的数量,之后再保证没有通过的和通过的数量的增量都是正的,根据这点来二分就可以了。

#include <iostream>

using namespace std;

typedef long long LL;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    LL x, y, p, q;
    cin >> t;
    while (t--) {
        LL cnt = 0;
        cin >> x >> y >> p >> q;
        if ((p == q && x != y) || (p == 0 && x != 0)) {
            cout << -1 << "\n";
            continue;
        }
        LL diff = y - x;
        LL d2 = q - p;
        LL l = 1, r = 1e9;
        while (l < r) {
            LL mid = (l + r) >> 1;
            if (mid * d2 < diff || mid * p < x) l = mid + 1;
            else r = mid;
        }
        cout << l * (q - p) - y + x + l * p - x << "\n";
    }
    return 0;
}

 

【CodeForces-1029F】Multicolored Markers

【CodeForces-1029F】Multicolored Markers

Solution:

内部各自至少也要有一个是矩形,我们首先将可能的矩形存下来,之后枚举大矩形的时候判断一下它是否可能嵌套小矩形来决定当前方案是否可行就可以。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

inline LL mini(LL a, LL b) {return a < b ? a : b;}

vector<LL> boxa, boxb;

int main(void) {
    LL a, b;
    scanf("%lld%lld", &a, &b);
    LL area = a + b;
    LL lim = sqrt(a);
    for (int i = 1; i <= lim; i++) {
        if (a % i == 0) boxa.push_back(i);
    }
    lim = sqrt(b);
    for (int i = 1; i <= lim; i++) {
        if (b % i == 0) boxb.push_back(i);
    }
    lim = sqrt(area);
    // cout << lim << endl;
    LL ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= lim; i++) {
        if (area % i) continue;
        LL tmp = area / i;
        for (int j = 0; j < boxa.size(); j++) {
            if (boxa[j] <= i && a / boxa[j] <= tmp) {
                ans = mini((i + tmp) * 2, ans);
                break;
            }
        }
        for (int j = 0; j < boxb.size(); j++) {
            if (boxb[j] <= i && b / boxb[j] <= tmp) {
                ans = mini((i + tmp) * 2, ans);
                break;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

 

【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

问题链接:https://vjudge.net/problem/UVA-1597

Solution:

由于输出要求大多是按照行为单位的,所以我们使用vector来记录行,并且记录清楚行号、文章号,之后将每个句子中的单词转化成小写字母,之后拆分出来,存到一个map中,map的值是一个集合,表示这个单词出现在对应的vector中的哪些句子记录中。拆分函数cutstr()十分关键。

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>
#define DBG

using namespace std;

struct Centence {
    string str;
    int idx;
    int pos;
};

vector<Centence> datas;
struct cmp {
    bool operator()(const int a, const int b) const {
        if (datas[a].idx != datas[b].idx) return datas[a].idx < datas[b].idx;
        else if (datas[a].pos != datas[b].pos) return datas[a].pos < datas[b].pos;
        return a < b;
    }
};

inline void tolow(string &str) {
    for (int i = 0; i < str.size(); i++)
        if (isalpha(str[i])) str[i] = tolower(str[i]);
}
string in, out;
int cut_i;
inline bool cutstr(const string s) {
    if (s != "") in = s, cut_i = 0;
    if (cut_i == in.size()) return false;
    out = "";
    for (int cnt = 0; cut_i < in.size() && cnt < 2; cut_i++) {
        if (cnt == 0 && isalpha(in[cut_i])) cnt = 1;
        else if (cnt == 1 && !isalpha(in[cut_i])) cnt = 2;
        if (cnt == 1) out += in[cut_i];
    }
    if (out == "") return false;
    else return true;
}

map<string, set<int, cmp> > wordIdx;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, m;
    cin >> n;
    string tmp, t;
    Centence c;
    int cnt = 0;
    getline(cin, tmp);
    for (int i = 0; cnt < n; i++) {
        getline(cin, tmp);
        if (tmp == "**********") {
            cnt++;
            i--;
            continue;
        }
        c.str = tmp, c.idx = cnt, c.pos = i;
        datas.push_back(c);
        stringstream ss;
        ss << tmp;
        while (ss >> t) {
            tolow(t);
            cutstr(t);
            do {
                if (!wordIdx.count(out)) wordIdx[out] = set<int, cmp>();
                wordIdx[out].insert(datas.size() - 1);
            } while (cutstr(""));
        }
    }
    cin >> m;
    string str;
    getline(cin, str);
    bool flag = true;
    while (m--) {
        getline(cin, str);
        stringstream ss;
        ss << str;
        t = "";
        ss >> tmp >> t;
        flag = true;
        if (t == "AND") {
            ss >> t;
            tolow(tmp), tolow(t);
            set<int, cmp> sa, sb, sc;
            sa = wordIdx[tmp], sb = wordIdx[t];
            for (int x : sa)
                for (int y : sb)
                    if (datas[x].idx == datas[y].idx) sc.insert(x), sc.insert(y);
            int pre;
            if (sc.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sc.begin()].idx;
            for (auto x : sc) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
        } else if (t == "OR") {
            ss >> t;
            tolow(tmp), tolow(t);
            set<int, cmp> sa, sb;
            sa = wordIdx[tmp], sb = wordIdx[t];
            for (int x : sb) sa.insert(x);
            int pre;
            if (sa.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sa.begin()].idx;
            for (auto x : sa) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
        } else if (tmp == "NOT") {
            tolow(t);
            set<int, cmp> sa = wordIdx[t];
            set<int> sb;
            for (int x : sa) {
                sb.insert(datas[x].idx);
            }
            int pre;
            if (sb.size() == n) cout << "Sorry, I found nothing.\n";
            else {
                bool flag = false;
                for (int i = 0; i < datas.size(); i++) {
                    if (sb.count(datas[i].idx)) continue;
                    if (flag && datas[i].idx != pre) cout << "----------\n";
                    else flag = true;
                    pre = datas[i].idx;
                    cout << datas[i].str << "\n";
                }
            }
            cout << "==========\n";
        } else {
            tolow(tmp);
            set<int, cmp> sa = wordIdx[tmp];
            int pre;
            if (sa.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sa.begin()].idx;
            for (auto x : sa) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
            flag = false;
        }
    }
    return 0;
}

 

【codeforces-1020A】New Building for SIS

【codeforces-1020A】New Building for SIS

爬楼的策略:

1.一栋楼上,不用考虑楼之间通道位置,直接去对应楼层。

2.楼与楼之间,如果两个位置都不在有通道的楼层,应当都寻找最近的通道楼层,耗时应当是两边各自到这个楼层的时间+穿越几栋楼的时间;如果任意一个位置在有通道的楼层,无论选择如何去目标位置,竖直方向最短距离都是两层的差值。

#include <iostream>
#include <cmath>

using namespace std;

inline bool inRange(int x, int a, int b) {
    return x >= a && x <= b;
}

int main(void) {
    int n, h, a, b, k, f1, t1, f2, t2;
    scanf("%d%d%d%d%d", &n, &h, &a, &b, &k);
    while (k--) {
        scanf("%d%d%d%d", &t1, &f1, &t2, &f2);
        if (t1 == t2) {
            printf("%d\n", abs(f1 - f2));
        } else {
            if (inRange(f1, a, b) || inRange(f2, a, b))
                printf("%d\n", abs(f1 - f2) + abs(t1 - t2));
            else
                printf("%d\n", min(abs(f1 - a) + abs(f2 - a), abs(f1 - b) + abs(f2 - b))
                    + abs(t1 - t2));
        }
    }
    return 0;
}

 

【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

问题链接:https://vjudge.net/problem/UVA-10087

Solution:

关于幻方构造,阅读:幻方的构造方法

除了二阶幻方不存在外,这道题只要在判断要求的一个方向上所有数的和减去标准幻方一个方向上所有数的和【标准幻方求和公式,对于n阶幻方,\(Sum = \frac{n * (n^2 + 1)}{2}】后是否是[latex]n^2\)的倍数就好,如果是,则可以通过给每个方格加上相同的一定数,获得要求的方阵。

#include <iostream>

using namespace std;

typedef long long LL;
const int LIM = 101;
struct Matrix {
    int v[LIM][LIM];
    int size;
};

inline LL getSum(LL n) {
    return n * (n * n + 1) / 2;
}

Matrix odd_msquare(int n) {
    Matrix ret = {{0}, n};
    int lim = n * n;
    int r = 0, c = n / 2;
    for (int i = 1; i <= lim; i++) {
        ret.v[r][c] = i;
        int nr = (r - 1 + n) % n;
        int nc = (c + 1 + n) % n;
        if (ret.v[nr][nc]) r++;
        else r = nr, c = nc;
    }
    return ret;
}

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

Matrix m4_msquare(int n) {
    Matrix ret = {{0}, n};
    int crt = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ret.v[i][j] = crt;
            crt++;
        }
    }
    int lim = n / 2;
    for (int i = 0; i < lim; i += 4) {
        for (int j = 0; j < n; j += 4) {
            if (i + 2 == lim && j > lim) break;
            if (j + 2 == lim && i + 2 == lim) {
                for (int k = 0; k < 2; k++) {
                    for (int m = 0; m < 4; m++) {
                        if (k == m || k == 4 - m - 1)
                            swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
                    }
                }
            } else {
                for (int k = 0; k < 4; k++) {
                    for (int m = 0; m < 4; m++) {
                        if (k == m || k == 4 - m - 1)
                            swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
                    }
                }
            }
        }
    }
    return ret;
}

Matrix m4p2_msquare(int n) {
    int m = (n - 2) / 4;
    Matrix tmp = odd_msquare(n / 2), ret = {{0}, n};
    for (int i = 0; i < tmp.size; i++)
        for (int j = 0; j < tmp.size; j++)
            tmp.v[i][j] = tmp.v[i][j] * 4 - 4;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j < tmp.size; j++) {
            ret.v[i << 1][j << 1] = 4 + tmp.v[i][j];
            ret.v[i << 1][(j << 1) + 1] = 1 + tmp.v[i][j];
            ret.v[(i << 1) + 1][j << 1] = 2 + tmp.v[i][j];
            ret.v[(i << 1) + 1][(j << 1) + 1] = 3 + tmp.v[i][j];
        }
    }
    ret.v[m << 1][tmp.size - 1] = 1 + tmp.v[m][tmp.size >> 1];
    ret.v[m << 1][tmp.size] = 4 + tmp.v[m][tmp.size >> 1];
    ret.v[(m << 1) + 1][tmp.size - 1] = 2 + tmp.v[m][tmp.size >> 1];
    ret.v[(m << 1) + 1][tmp.size] = 3 + tmp.v[m][tmp.size >> 1];
    for (int j = 0; j < tmp.size; j++) {
        ret.v[(m + 1) << 1][j << 1] = 1 + tmp.v[m + 1][j];
        ret.v[(m + 1) << 1][(j << 1) + 1] = 4 + tmp.v[m + 1][j];
        ret.v[((m + 1) << 1) + 1][j << 1] = 2 + tmp.v[m + 1][j];
        ret.v[((m + 1) << 1) + 1][(j << 1) + 1] = 3 + tmp.v[m + 1][j];
    }
    ret.v[(m + 1) << 1][tmp.size - 1] = 4 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[(m + 1) << 1][tmp.size] = 1 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[((m + 1) << 1) + 1][tmp.size - 1] = 2 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[((m + 1) << 1) + 1][tmp.size] = 3 + tmp.v[m + 1][tmp.size >> 1];
    for (int i = m + 2; i < tmp.size; i++) {
        for (int j = 0; j < tmp.size; j++) {
            ret.v[i << 1][j << 1] = 1 + tmp.v[i][j];
            ret.v[i << 1][(j << 1) + 1] = 4 + tmp.v[i][j];
            ret.v[(i << 1) + 1][j << 1] = 3 + tmp.v[i][j];
            ret.v[(i << 1) + 1][(j << 1) + 1] = 2 + tmp.v[i][j];
        }
    }
    return ret;
}

int main(void) {
    LL s;
    int n;
    Matrix ans;
    while (~scanf("%d%lld", &n, &s)) {
        if (n == 1) printf("%10lld\n", s);
        else if (n == 2) printf("You can't be like Shahjahan!\n");
        else {
            LL diff = s - getSum(n);
            if (diff % n) printf("You can't be like Shahjahan!\n");
            else {
                LL add = diff / n;
                if (n % 2) {
                    ans = odd_msquare(n);
                } else {
                    if (n % 4) ans = m4p2_msquare(n);
                    else ans = m4_msquare(n);
                }
                for (int i = 0; i < ans.size; i++) {
                    for (int j = 0; j < ans.size; j++) {
                        if (j) putchar(' ');
                        printf("%10lld", ans.v[i][j] + add);
                    }
                    putchar('\n');
                }
            }
        }
        putchar('\n');
    }
    return 0;
}

 

【HDU-4990】Reading comprehension

【HDU-4990】Reading comprehension

Solution:

看上去是分奇偶的,但是具有统一的递推形式:

记\(a_k\)为第k项的值。

Part 1.当k是偶数时,则\(a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1\)。

Part 2.当k是奇数时,则\(a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1\)。

写出变换矩阵就可以解决了。

#include <iostream>

using namespace std;

typedef long long LL;
LL MOD;
struct Matrix {
    LL t[3][3];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n;
    while (cin >> n >> MOD) {
        if (n == 1) cout << 1 % MOD << "\n";
        else if (n == 2) cout << 2 % MOD << "\n";
        else {
            Matrix trans = powMod(n - 2, BASE);
            LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}

 

 

【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution:

看到这道题,最先想说233333…

最先考虑到的方法,当然是直接暴力推,反正每个位置只与它左侧及上侧有关,推到要求的那个位置上就好,但是这样单组数据复杂度是\(O(nm)\),虽然有5000ms,但是一般这种题目数据量会很大,这样暴力绝对会超时,于是考虑到需要更快的迭代方法,第一列依次是\(0, a_1, a_2… a_n\),尝试在纸上把这个矩阵列出来,并且把每个位置上的值都只使用这些已知符号代替,我们发现一个规律,每个位置上的数实际上都把这一列它上方的所有数都加了进来,同理也把它左边的所有数都加了进来,进行简单的整理后,我们发现:每一行可以仅由上一行的值推出,每一列也可以仅由上一列的值推出。由上一行推的时候需要考虑到一个与输入相关的无规律常数,这个常数的存在破坏了递推形式不变性,所以只能够用刚才\(O(nm)\)复杂度的方法推;而由上一列推这一列时,我们需要考虑一个题目中拟定的嘲讽一般的233,它的规律很明显,由上一列到这一列,它的值扩10倍后加3便可完成这次递推,唯一不满足的就是最前面那一列的0。这时,注意到,在整个矩阵中,左上角的0是唯一一个不对结果产生贡献的值(并不是因为它是0,而是因为根据题设递推规则,它没有被加入到\(a_{nm}\)中),这样,它的值可以任意修改,那么我们便修改成23,这时每一列之间的递推形式固定的了下来,可以写出变换矩阵,之后使用矩阵快速幂来求解,复杂度降到\(O(n^3logm)\)。

总结一下,这道题关键是:

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果,是题设故意设计的一个坑。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 10000007;
const int LIM = 15;
struct Matrix {
    LL t[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}, size};
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
};

Matrix buildBase(int size) {
    Matrix ret = {{0}, size};
    ret.t[size - 1][size - 1] = 1;
    for (int i = size - 2; i >= 0; i--) {
        ret.t[i][0] = 10;
        ret.t[i][size - 1] = 1;
        for (int j = 1; j <= i; j++)
            ret.t[i][j] = 1;
    }
    return ret;
}

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{0}, m.size};
    for (int i = 0; i < ret.size; i++)
        ret.t[i][i] = 1;
    while (pow) {
        if (pow & 1) ret = ret * m;
        m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, m;
    LL ori[LIM];
    while (cin >> n >> m) {
        ori[0] = 23;
        ori[n + 1] = 3;
        for (int i = 1; i <= n; i++) cin >> ori[i];
        if (m == 0) cout << ori[n] << "\n";
        else {
            Matrix trans = powMod(m, buildBase(n + 2));
            LL ans = 0;
            for (int i = 0; i <= n + 1; i++)
                ans = (ans + trans.t[n][i] * ori[i]) % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}