P1

51nod 2574 三角形计数

#include <bits/stdc++.h>
using namespace std;
char s[1000020];
int main() {
    scanf("%s", s);
    int l = strlen(s);
    long long ans = (long long)(l - 1) / 2 * l;
    if (l % 2 == 1) {
        long long cnt0 = 0;
        long long cnt1 = 0;
        for (int i = 0; i < l; i++) {
            if (s[i] == '1') {
                cnt1++;
            } else {
                cnt0++;
            }
        }
        ans -= cnt0 * cnt1 * 3 / 2;
    } else {
        long long cnt00 = 0, cnt01 = 0;
        long long cnt10 = 0, cnt11 = 0;
        for (int i = 0; i < l; i += 2) {
            if (s[i] == '1') {
                cnt01++;
            } else {
                cnt00++;
            }
        }
        for (int i = 1; i < l; i += 2) {
            if (s[i] == '1') {
                cnt11++;
            } else {
                cnt10++;
            }
        }
        ans -= (cnt00 * cnt01 + cnt10 * cnt11) * 2;
        ans -= (cnt00 * cnt11 + cnt10 * cnt01);
        for (int i = 0; i < l / 2; i++) {
            if (s[i] != s[(i + l / 2) % l]) {
                ans++;
            }
        }
    }
    if (l % 3 == 0) {
        ans -= l / 3 * 2;
        for (int i = 0; i < l; i++) {
            if (s[i] != s[(i + (l / 3)) % l]) {
                ans++;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

P2

P3