某島

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

POI XIII Stage 3. Problem Crystals

Brief description:

給定一個 n 個元素的數組 {ai}, 問存在多少組 {xi, xi <= ai && 所有 xi 的 xor 和 等於 0}。。。 ( n <= 50 .. )

亦或和等於 0 和等於 k 的版本幾乎沒有區別,討論前者。

這類題目的解法是從高到低按位分階段組合 DP .. .
我們的目的是,在每輪的 DP 過後,這一位上所有至少 Skip 一位的組合,全部被計數,這樣做之後,剩下的所有還沒有被計數的情況(沒有發生 Skip)就會形成一個結構相同的子問題 …

額,還沒有定義 Skip …

我們討論當前掃描的是最高位 … 對於那些在這一位上是 1 的元素,這些元素有兩種決策:
分別 是取 1 和取 0,我們稱那些含有 1 的元素,取 0 的決策為 折越 (Skip) …

那麼對於當前第 i 位,掃描了 j 個數字,我們設計狀態 f[0], f[1], f[2] 分別為
從未發生過 折越 、發生過奇數次 折越、和發生過偶數次 折越 且不包括 f[0]。

分類討論 dp 。。。

#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);
            }
        }
 
…

之後,我們考慮含有 1 的個數的奇偶性,
如果含有奇數個1,那麼我們前面所說沒有發生過一次 折越 (Skip) 的情況就不會出現在計數方案中,因此直接跳出。
每一位的複雜度為 O(n) ,總的複雜度為 O(nb),b 表元素的二進位位數 … (最後邊界處別忘了所有元素都為 0 的話也是一組解 .. .)


.
.

(另,推公式的過程中還有一個難點,具體的說來是這樣,對於當前掃描到第 i 位,一個發生了 k 次 折越 的狀態,是需要保證 (i, 0] 位上的亦或和為 0 的。
因為發生 折越 的位置之後的二進位位可以任意組合,所以如果固定了其中的任意 k-1 個元素的狀態,總可以設置一種第 k 個元素的狀態,使得 (i, 0] 位上的亦或和為 0,這也是組合 dp 可以奏效的依據。)


/* …………………………………………………………………………………………………………………. */
/** Header **/
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <list>
#include <set>
#include <map>
using namespace std;
/** Repeat **/
#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);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<N____;++I)
#define FOR_C(I, A, B) for (int B____=int(B),I=A;I<B____;++I)
#define DWN_C(I, B, A) for (int A____=int(A),I=B-1;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<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)
#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)
#define SQZ(I, J, A, B) for (int I=int(A),J=int(B)-1;I<J;++I,–J)
#define SQZ_1(I, J, A, B) for (int I=int(A),J=int(B);I<=J;++I,–J)
/** Micro Mezzo Macro Flation — Overheated Economy **/
#define ALL(A) A.begin(), A.end()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define BSC(A, X) find(ALL(A), X) // != A.end()
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define Rush int T____; RD(T____); DO(T____)
#pragma comment(linker, "/STACK:36777216")
#define Ruby system("ruby main.rb")
#define Haskell system("runghc main.hs")
#define Pascal system("fpc main.pas")
/** Typedef **/
typedef long long LL;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VD;
typedef set<int> SI;
typedef set<string> SS;
typedef set<LL> SL;
typedef set<DB> SD;
typedef map<int, int> MI;
typedef map<string, int> MS;
typedef map<LL, int> ML;
typedef map<DB, int> MD;
typedef pair<int, int> PII;
typedef pair<int, bool> PIB;
typedef vector<PII> VII;
typedef set<PII> SII;
typedef map<PII, int> MII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
/** I/O Accelerator **/
/* … :" We are I/O Accelerator … Use us at your own risk 😉 … " .. */
template<class T> 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<class T> inline void OT(const T &x){
cout << x << endl;
//printf("%d\n", x);
//printf("%.2lf", x);
//printf("Case %d: %d", ____T, ans)
}
template<class T> 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<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> 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<class T0, class T1, class T2, class T3, class T4, class T5, class T6> 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<class T0, class T1> inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> 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<class T0, class T1, class T2, class T3, class T4, class T5, class T6> 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<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> 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<class T0, class T1, class T2, class T3, class T4, class T5, class T6> 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<class T> inline void CLR(T &A){A.clear();}
template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}
template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> 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<class T0, class T1, class T2, class T3, class T4, class T5, class T6> 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<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}
template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2){FLC(A0), FLC(A1), FLC(A2);}
template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3){FLC(A0), FLC(A1), FLC(A2), FLC(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> 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<class T0, class T1, class T2, class T3, class T4, class T5, class T6> 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<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
template<class T> inline T sqr(T x){return x * x;}
inline bool _1(int x, int i){return x & 1<<i;}
inline int _1(int i){return 1<<i;}
inline int _U(int i){return _1(i) – 1;};
/* …………………………………………………………………………………………………………………. */
const int N = 50;
UINT a[N]; ULL ans;
int n, k;
#define c ((a[j] & _U(i)) + 1)
#define g (1 << i)
void solve() {
ULL f[3]; int t; DWN(i, 32 ,0) {
t = 0, f[0] = 1, f[1] = 0, f[2] = 0; //#
REP(j, n){
if (_1(a[j], i)) {
ULL w1 = f[0] + f[2] * g, w2 = f[1] * g; t ^= 1;
f[0] *= c, f[1] *= c, f[2] *= c;
f[1] += w1, f[2] += w2;
}
else {
f[0] *= c, f[1] *= c, f[2] *= c;
}
}
if (t) {
ans += f[1] – 1;
return;
}
ans += f[2];
}
}
int main() {
//freopen("D.in", "r", stdin);
//freopen("D.out", "w", stdout);
//ios::sync_with_stdio(false);
RD(n); REP(i, n) RD(a[i]);
solve(), OT(ans);
}

view raw

Crystals.cpp

hosted with ❤ by GitHub

http://www.lydsy.com/JudgeOnline/problem.php?id=1442
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=384&problem=3102&mosmsg=Submission+received+with+ID+856655
http://main.edu.pl/en/archive/oi/13/kry
SRM 508 DIV 1 Level 2. YetAnotherORProblem
http://hi.baidu.com/%D2%BB%CE%BB%C1%E3/blog/item/603ee5b68bf283e630add144.html
http://blog.163.com/fjxmlhx@126/blog/static/144072841201022492458853/