题目链接：https://cn.vjudge.net/problem/Gym-101612B
Problem B. Boolean Satisfiability
Input file: boolean.in Time limit: 3 seconds
Output file: boolean.out Memory limit: 512 megabytes
Boolean satisfiability problem (SAT) is known to be a very hard problem in computer science. In this
problem you are given a Boolean formula, and you need to find out if the variables of a given formula can
be consistently replaced by the values true or false in such a way that the formula evaluates to true.
SAT is known to be NP-complete problem. Moreover, it is NP-complete even in case of 3-CNF formula
(3-SAT). However, for example, SAT problem for 2-CNF formulae (2-SAT) is in P#SAT is the extension of SAT problem. In this problem you need to check if it is possible, and count the
number of ways to assign values to variables. This problem is known to be #P-complete even for 2-CNF
formulae. We ask you to solve #1-DNF-SAT, which is #SAT problem for 1-DNF formulae.
You are given a Boolean formula in 1-DNF form. It means that it is a disjunction (logical or) of one or
more clauses, each clause is exactly one literal, each literal is either variable or its negation (logical not).
Formally:
⟨formula⟩ ::= ⟨clause⟩ | ⟨formula⟩ ∨ ⟨clause⟩
⟨clause⟩ ::= ⟨literal⟩
⟨literal⟩ ::= ⟨variable⟩ | ¬ ⟨variable⟩
⟨variable⟩ ::= A … Z | a … z
Your task is to find the number of ways to replace all variables with values true and false (all occurrences
of the same variable should be replaced with same value), such that the formula evaluates to true.
Input
The only line of the input file contains a logical formula in 1-DNF form (not longer than 1000 symbols).
Logical operations are represented by ‘|’ (disjunction) and ‘~’ (negation). The variables are ‘A’ … ‘Z’
and ‘a’ … ‘z’ (uppercase and lowercase letters are different variables). The formula contains neither
spaces nor other characters not mentioned in the grammar.
Output
Output a single integer — the answer for #SAT problem for the given formula.
Examples
boolean.in boolean.out
a 1
B|~B 2
c|~C 3
i|c|p|c 7

题目大意：求使一个布尔表达式为真值的所有情况数
做法：我们可以这样考虑。既然变量之间都是或关系，那么当从未出现过~a|a是，只有一种情况使式子为0，即所有变量全取零，这时只需统计所有变量个数即可，否则无论所有变量取任何值，式子均取真值。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+7;
bool pos[256],neg[256];
char str[maxn];
int main()
{
    freopen("boolean.in","r",stdin);
    freopen("boolean.out","w",stdout);
     while(~scanf("%s",str))
     {
         memset(pos,0,sizeof(pos));
         memset(neg,0,sizeof(neg));
         bool flag = true;//标记是否出现a|~a的情况
         for(int i=0;str[i];i++)
         {
             if(str[i]=='|')continue;
             if(str[i]=='~')
             {
                 neg[str[++i]] = true;
                 if(pos[str[i]])flag = false;
             }
             else
             {
                 pos[str[i]] = true;
                 if(neg[str[i]])flag = false;
             }
         }
         int k=0;
         for(int i=0;i<256;i++)
         {
             if(pos[i]||neg[i])++k;
         }
         if(flag)printf("%lld\n",(1LL<<k)-1);
         else printf("%lld\n",(1LL<<k));
     }
    return 0;

}