某岛

… : "…アッカリ～ン . .. . " .. .
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/

Posted by xiaodao
Category: BZOJ

« | »

  • Archives

    open all | close all