# 某岛

… : "…アッカリ～ン . .. . " .. .
September 7, 2013

# POI XIII Stage 3. Problem Crystals

### Brief description:

```#define c ((a[j] & _U(i)) + 1)
#define g (1 << i)

…

REP(j, n){
if (_1(a[j], i)) {
int w1 = sum(f[0], pdt(f[2], g)), w2 = pdt(f[1], g); t ^= 1;
MUL(f[0], c), MUL(f[1], c), MUL(f[2], c);
INC(f[1], w1), INC(f[2], w2);
}
else {
MUL(f[0], c), MUL(f[1], c), MUL(f[2], c);
}
}

…
```

.
.

（另，推公式的过程中还有一个难点，具体的说来是这样，对于当前扫描到第 i 位，一个发生了 k 次 折越 的状态，是需要保证 (i, 0] 位上的亦或和为 0 的。

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 /* …………………………………………………………………………………………………………………. */ /** Header **/ #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /** Repeat **/ #define REP(I, N) for (int I=0;I=int(A);–I) #define REP_1(I, N) for (int I=1;I<=int(N);++I) #define FOR_1(I, A, B) for (int I=int(A);I<=int(B);++I) #define DWN_1(I, B, A) for (int I=int(B);I>=int(A);–I) #define REP_C(I, N) for (int N____=int(N),I=0;I=A____;–I) #define REP_1_C(I, N) for (int N____=int(N),I=1;I<=N____;++I) #define FOR_1_C(I, A, B) for (int B____=int(B),I=A;I<=B____;++I) #define DWN_1_C(I, B, A) for (int A____=int(A),I=B;I>=A____;–I) #define DO(N) while(N–) #define DO_C(N) int N____ = N; while(N____–) #define TO(i, a, b) int s_=a VI; typedef vector VS; typedef vector VL; typedef vector VD; typedef set SI; typedef set SS; typedef set SL; typedef set SD; typedef map MI; typedef map MS; typedef map ML; typedef map MD; typedef pair PII; typedef pair PIB; typedef vector VII; typedef set SII; typedef map MII; typedef vector VVI; typedef vector VVII; /** I/O Accelerator **/ /* … :" We are I/O Accelerator … Use us at your own risk 😉 … " .. */ template inline void RD(T &x){ cin >> x; //scanf("%d", &x); //char c; for (c = getchar(); c < '0'; c = getchar()); x = c – '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c – '0'; //char c; c = getchar(); x = c – '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c – '0'; } template inline void OT(const T &x){ cout << x << endl; //printf("%d\n", x); //printf("%.2lf", x); //printf("Case %d: %d", ____T, ans) } template inline T& _RD(T &x){ RD(x); return x;} inline int RD(){ int x; RD(x); return x;} inline LL RD_LL(){ int x; RD(x); return x;} inline DB RD_DB(){ DB x; RD(x); return x;} template inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);} template inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);} template inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);} template inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);} template inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);} template inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);} template inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);} template inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);} template inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);} template inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);} template inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);} template inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);} template inline void RST(T &A){memset(A, 0, sizeof(A));} template inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);} template inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);} template inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);} template inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);} template inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);} template inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);} template inline void CLR(T &A){A.clear();} template inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);} template inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);} template inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);} template inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);} template inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);} template inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);} template inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);} template inline void FLC(T &A, int x){memset(A, x, sizeof(A));} template inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);} template inline void FLC(T0 &A0, T1 &A1, T2 &A2){FLC(A0), FLC(A1), FLC(A2);} template inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3){FLC(A0), FLC(A1), FLC(A2), FLC(A3);} template inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);} template inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);} template inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);} /** Add – On **/ const int MOD = 1000000003; const int INF = 0x7fffffff; template inline void checkMin(T &a, T b){if (b inline void checkMax(T &a, T b){if (b>a) a=b;} template inline T sqr(T x){return x * x;} inline bool _1(int x, int i){return x & 1<

view raw

Crystals.cpp

hosted with ❤ by GitHub

http://www.lydsy.com/JudgeOnline/problem.php?id=1442