本文共 4715 字，大约阅读时间需要 15 分钟。
一开始是没想到观察题的。只想到直接矩阵快速幂。
但是超时了，因为我的矩阵快速幂是应对稀疏矩阵的，
因为当时做这题的时候，以前的矩阵快速幂模板超时，所以就换了个，但是这题用稀疏矩阵的模板会超时，所以就把两个模板都收录算了。但是时间是1.58s，现在是pertest。所以后面的可能会超时，然而这题应该直接观察，其实也不算观察，算数学吧。鸽笼原理
前3项固定，最多1/2 * 1/2 * 1/2 项后，就会和前3项重复。
然后算一算，就发现了重复了。
#include #include #include #include #include #include #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include int n;const int maxn = 2000 + 20;char str[maxn][maxn];int ans[4];int f[] = { 0, 1, 0, 1, 0, 0, 1, 1};void init() { for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { if (i == 1 && j == 1) continue; LL val = (1LL * i * j) * (1LL * i * j); val %= 7; if (val == 0) val = 7; if (f[val] == 1) { str[i][j] = 'Y'; } else str[i][j] = 'X'; }// cout << endl; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i - 1; ++j) { str[i][j] = str[j][i]; } }// for (int i = 1; i <= n; ++i) {// for (int j = 1; j <= n; ++j) {// cout << str[i][j];// }// cout << endl;// } //90 int p1 = n, p2 = 1; for (int i = 1; i <= n; ++i) { p1 = n; p2 = i; for (int j = 1; j <= n; ++j) { if (str[i][j] != str[p1--][p2]) { ans[1]++; } } p1 = n - i + 1; p2 = n; for (int j = 1; j <= n; ++j) { if (str[i][j] != str[p1][p2--]) { ans[2]++; } } p1 = n - i + 1; for (int j = 1; j <= n; ++j) { if (str[i][j] != str[p1][j]) { ans[3]++; } } }}void work() { int q; scanf("%d%d", &n, &q); init(); while (q--) { int x; scanf("%d", &x);// cin >> x; x %= 360; x /= 90;// cout << ans[x] << endl; printf("%d\n", ans[x]); }}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif work(); return 0;}
#include #include #include #include #include #include #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include int n;const int maxn = 2000 + 20;char str[maxn][maxn];struct Matrix { LL a[4][4]; int row; int col;};//struct Matrix matrix_mul(struct Matrix a, struct Matrix b, int MOD) {// struct Matrix c = {0};// c.row = a.row;// c.col = b.col;// for (int i = 1; i <= a.row; ++i) {// for (int k = 1; k <= a.col; ++k) {// if (a.a[i][k]) {// for (int j = 1; j <= b.col; ++j) {// c.a[i][j] += a.a[i][k] * b.a[k][j];//// c.a[i][j] = (c.a[i][j] + MOD) % MOD;// }// c.a[i][j] %= MOD;// }// }// }// return c;//}struct Matrix matrix_mul (struct Matrix a, struct Matrix b, int MOD) { struct Matrix c = { 0}; c.row = a.row; c.col = b.col; for (int i = 1; i <= a.row; i++) { for (int j = 1; j <= b.col; j++) { for (int k = 1; k <= b.row; k++) { c.a[i][j] += a.a[i][k] * b.a[k][j]; } c.a[i][j] = (c.a[i][j] + MOD) % MOD; } } return c;}struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, LL n, int MOD) { while (n) { if (n & 1) { ans = matrix_mul(ans, base, MOD); } n >>= 1; base = matrix_mul(base, base, MOD); } return ans;}int ans[4];void init() { struct Matrix A; A.row = 1; A.col = 3; A.a[1][1] = 1; A.a[1][2] = 2; A.a[1][3] = 3; struct Matrix B; B.col = B.row = 3; B.a[1][1] = 0; B.a[1][2] = 0; B.a[1][3] = 3; B.a[2][1] = 1; B.a[2][2] = 0; B.a[2][3] = 2; B.a[3][1] = 0; B.a[3][2] = 1; B.a[3][3] = 1; str[1][1] = 'Y';// cout << "1" << " "; for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { if (i == 1 && j == 1) continue; LL val = (1LL * i * j) * (1LL * i * j);// cout << val << " "; struct Matrix t = quick_matrix_pow(A, B, val - 3, 2);// cout << B.a[2][3] << " "; if (t.a[1][3] & 1) { str[i][j] = 'Y'; } else str[i][j] = 'X';// cout << t.a[1][3] << " "; }// cout << endl; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i - 1; ++j) { str[i][j] = str[j][i]; } }// for (int i = 1; i <= n; ++i) {// for (int j = 1; j <= n; ++j) {// cout << str[i][j];// }// cout << endl;// } //90 int p1 = n, p2 = 1; for (int i = 1; i <= n; ++i) { p1 = n; p2 = i; for (int j = 1; j <= n; ++j) { if (str[i][j] != str[p1--][p2]) { ans[1]++; } } p1 = n - i + 1; p2 = n; for (int j = 1; j <= n; ++j) { if (str[i][j] != str[p1][p2--]) { ans[2]++; } } p1 = n - i + 1; for (int j = 1; j <= n; ++j) { if (str[i][j] != str[p1][j]) { ans[3]++; } } }}void work() { int q; cin >> n >> q; init(); while (q--) { int x; cin >> x; x %= 360; x /= 90; cout << ans[x] << endl; }}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif IOS; work(); return 0;}
转载于:https://www.cnblogs.com/liuweimingcprogram/p/6211053.html
