Codeforces Round #305 (Div. 1), problem: (C) Mike and Foam

排容w

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int int64;

vector<int> primes;
vector<int> radi[5000001];
bool has[200000] = {0};
int has_count = 0;
int arr[200000];
int64 tab[500001] = {0};

void dump(int n){
    printf("radical %d : ", n);
    for(int ii : radi[n])
        printf("%d ", ii);
    puts("");
    return;
}

int main(){
    
    {vector<bool> seive(500000, 0);
    for(int lx = 2;lx < 500000;lx++)
        if(seive[lx] == 0)
            for(int ly = 2;ly*lx < 500000;ly++)
                seive[ly*lx] = 1;
    for(int lx = 2;lx < 500000;lx++)
        if(seive[lx] == 0)
            primes.push_back(lx);
    }
    for(int lx = 0;lx < primes.size();lx++){
        int p = primes[lx];
        for(int ly = 1;ly*p <= 500000; ly++)
            radi[ly*p].push_back(p);
    }

    int n, q; scanf("%d %d", &n, &q);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);
    
    int64 count = 0;
    while(q--){
        int _inp; scanf("%d", &_inp); _inp--;
        int inp = arr[_inp];

        //printf("q %d\n", inp);

        int pc = radi[inp].size();
    
        if(has[_inp] == 0){
            int64 aa = 0;
            for(int sts = 0;sts < (1<<pc);sts++){
                int val = 1;
                int64 sign = 1;
                for(int lx = 0;lx < pc;lx++)
                    if(sts&(1<<lx))
                        sign *= -1, val *= radi[inp][lx];
                aa += tab[val]*sign;
                tab[val]++;
            }
            count += aa;
        }else{
            int64 aa = 0;
            for(int sts = 0;sts < (1<<pc);sts++){
                int val = 1;
                int64 sign = 1;
                for(int lx = 0;lx < pc;lx++)
                    if(sts&(1<<lx))
                        sign *= -1, val *= radi[inp][lx];
                aa += (tab[val]-1)*sign;
                tab[val]--;
            }
            count -= aa;
        }
        has[_inp] ^= 1;
        printf("%I64d\n", count);
    }
    return 0;
}

BZOJ 1031: [JSOI2007]字符加密Cipher

翻了半天 才翻到這SA裸題

倍增算法N(lgN)^2

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

/**************************************************************     Problem: 1031     User: mudream4869     Language: C++     Result: Accepted     Time:1296 ms     Memory:3544 kb ****************************************************************/   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm>   using namespace std;   void dump(int n, int* arr){     for(int lx = 0;lx < n;lx++)         printf("%d ", arr[lx]);     puts("");     return; }   char buf[200010], ret[200010]; int rnk[2][200000]; int sa[200000];   struct CMP{     int* rk;     int n, len;     bool operator()(const int& i, const int& j){         if(rk[i] != rk[j]) return rk[i] < rk[j];         int a = (i+n < len) ? rk[i+n] : -1;         int b = (j+n < len) ? rk[j+n] : -1;         return a < b;     } };   void build_sa(){     int len = strlen(buf);     int now = 0;     for(int lx = 0;lx < len;lx++) rnk[0][lx] = buf[lx];     for(int lx = 0;lx < len;lx++) sa[lx] = lx;     for(int l = 2; l <= len;l<<=1){         CMP cmp = {rnk[now], l>>1, len};         sort(sa, sa+len, cmp);         rnk[now^1][sa[0]] = 0;         for(int lx = 1;lx < len;lx++)             rnk[now^1][sa[lx]] = rnk[now^1][sa[lx-1]] + cmp(sa[lx-1], sa[lx]);         now ^= 1;     }     return; }   int main(){     scanf("%s", buf);     int len = strlen(buf);     for(int lx = len;lx>=0;lx--) buf[lx+len] = buf[lx];     build_sa();     for(int lx = 0;lx < 2*len;lx++){         if(sa[lx] >= len) continue;         printf("%c", buf[sa[lx]+len-1]);     }     puts("");     return 0; }