# 题解

• 1的个数之和为偶数
• 1的个数最多的那个数的1的个数小于其他数1的个数的和（贪心）

# 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n = 0, ans = 0;
ll oddCnt = 0, evenCnt = 0;
ll s[300005] = {};
bool sumEven[300005] = {};

ll bitCnt(ll ori) {
ll cnt = 0;
while (ori) {
cnt += ori & 1;
ori >>= 1;
}
return cnt;
}

int main() {
cin >> n;
for (ll i = 0; i < n; ++i) {
cin >> s[i];
s[i] = bitCnt(s[i]);
}

ll sum = 0;
oddCnt = 0, evenCnt = 1, sumEven[n] = true;
for (ll i = n - 1; i >= 0; --i) {
sum += s[i];
if (sum & 1) {
ans += oddCnt;
oddCnt++;
} else {
ans += evenCnt;
sumEven[i] = true;
evenCnt++;
}
}

for (ll i = 0; i < n; ++i) {
ll sumx = 0, maxi = 0;
for (ll j = i; j < min(n, i + 64LL); ++j) {
if (s[j] > maxi) {
sumx += maxi;
maxi = s[j];
} else {
sumx += s[j];
}
if (sumx < maxi && sumEven[i] == sumEven[j + 1]) {
ans--;
}
}
}

cout << ans;
return 0;
}

# 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mt[100] = {};
ll mintree(int h, int d) {
if (h <= 0) return 0;
if (mt[h] >= 0) return mt[h];
else if (h == 1) return 1;
else return mt[h] = mintree(h - 1, d) + mintree(h - 1 - d, d) + 1;
}

int main() {
memset(mt, -1, sizeof(mt));
int n = 0, d = 0;
ll ans = 0;
scanf("%d%d", &n, &d);
if (n == 0) {
ans = 0;
} else {
ans = (1LL << (n - 1)) - 1 - mintree(n - 1 - d, d);
}
printf("%lld", ans);
}

# 题意

• $1 \leq T \leq 20$
• $0 \leq A, B, C, D \leq 10^9$
• $1 \leq P, n \leq 10^9$

# 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;

class matrix{
public:
ll s[3][3];

matrix(){
memset(s, 0, sizeof(s));
}
matrix(ll Fn, ll Fn1, ll E) {
s[0][0] = Fn;
s[0][1] = Fn1;
s[0][2] = E;
s[1][0] = s[1][1] = s[1][2] = 0;
s[2][0] = s[2][1] = s[2][2] = 0;
}
matrix(ll C, ll D) {
s[0][0] = D;
s[1][0] = C;
s[0][1] = s[2][0] = s[2][2] = 1;
s[0][2] = s[1][1] = s[1][2] = s[2][1] = 0;
}
};

matrix mul(matrix &a, matrix &b) {
matrix ret;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
ret.s[i][j] = (ret.s[i][j] + a.s[i][k] * b.s[k][j]) % modulo;
}
}
}
return ret;
}

ll A = 0, B = 0, C = 0, D = 0, P = 0, n = 0;

void xmul(ll &Fn, ll &Fn1, ll E, ll t) {
matrix ret(Fn, Fn1, E);
matrix b(C, D);
while (t) {
if (t & 1) {
ret = mul(ret, b);
}
b = mul(b, b);
t >>= 1;
}
Fn = ret.s[0][0];
Fn1 = ret.s[0][1];
}

ll solve() {
if (n == 1) return A;
if (n == 2) return B;
ll Fn1 = A, Fn = B, nex = 0, PN = 0;
matrix res;
for (ll i = 3; i <= n; ) {
PN = P / i;
if (PN == 0) {
nex = n;
} else {
nex = min(n, P / PN);
}
xmul(Fn, Fn1, PN, nex - i + 1);
i = nex + 1;
}
return Fn;
}

int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
printf("%lld\n", solve());
}
}

# 题意

• $2 \le N, M \le 2048$
• $1 \le P \le 64$
• $0 \le A_{ij} \le 65536$

# 思路

STFW看看有没有什么快速算矩阵的方法，没有

# 代码

#include <bits/stdc++.h>
using namespace std;

int n = 0, p = 0, m = 0, bk = 0;
int a[4200][70] = {};
int b[4200][70] = {};
int c[4200][4200] = {};
int apre[4200][10][260] = {};
int bpre[4200][10] = {};
char s[100] = {};

void pre() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < bk; ++j) {
for (int k = 0; k < 256; ++k) {
for (int p = 0; p < 8; ++p) {
if ((k >> p) & 1) {
apre[i][j][k] += a[i][(j << 3) + p];
}
}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < bk; ++j) {
for (int p = 0; p < 8; ++p) {
bpre[i][j] += b[i][(j << 3) + p] << p;
}
}
}
}

int getAns() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int p = 0; p < bk; ++p) {
c[i][j] += apre[i][p][bpre[j][p]];
}
}
}

int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j= 0; j < m; ++j) {
ans ^= c[i][j];
}
}
return ans;
}

int main() {
scanf("%d%d%d", &n, &p, &m), bk = ((p - 1) >> 3) + 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < p; ++j) {
scanf("%x", &a[i][j]);
}
}
for (int i = 0; i < m; ++i) {
scanf("%s", s);
for (int j = 0; j < p; ++j) {
b[i][j] = s[j] - '0';
}
}
pre();
printf("%d\n", getAns());
return 0;
}

# Contest

emmm……暴力穷举，AC。

## 第三大水题

### 思路

7
1 2
1 3
1 4
2 5
3 6
4 7


## 打铁感想

P.S. 不用PC^2用OJ还不给看已提交代码的我也当场去世了拜拜了您那