题目链接:https://atcoder.jp/contests/abc189/tasks/abc189_d

分享这题的目的是记录一个坑：整数常量会被编译器当成是int.所以当问题答案会超int的时候,会很容易疏忽.
做题的时候被这个点坑了接近一个小时,就想思路没问题呀？？？怎么就WA了....

思路1：

用dp的思路(其实就是一个递推),但是我当时想的就是递推.
dp[i][0] : 最后一位为0时，逻辑表达式结果为1的计数
dp[i][1] : 最后一位为1是，逻辑表达式结果为1的计数
1、当最后一个逻辑运算符为OR的时候:
最后一位是1，那么前面n-1为不管总结果是0/1,总的逻辑结果都是1，所以答案加上 1LL << n .(注意这里1要转成LL)
最后一位为0，前面n-1位的逻辑结果为1的才算答案，所以答案加上 dp[i-1][0] + dp[i-1][1]
总的来说：当从右到做第一位逻辑运算符为OR的时候：dp[i][0] = dp[i-1][0] + dp[i-1][1] ; dp[i][1] = lLL << n
2、当最后一个逻辑运算符为AND的时候：
最后一位为1,前面n-1位的总答案也必须为1，所以答案加上 dp[i-1][1] + dp[i-1][0]
最后一位为0，前面无论怎么样答案都为0
总的来说：dp[i][0] = 0; dp[i][1] = dp[i-1][1] + dp[i-1][0];
base case:
f[1][0] = 0,f[1][1] = 1;
f[1][0] = 1,f[1][1] = 2;
最终答案= dp[n][1] + dp[n][0]

思路1参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100;
int f[N][2];
vector<string> vc;
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("tpl.txt","r",stdin);
    #endif
    string line;
    int n ; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> line; vc.push_back(line);
    }
    if(vc[0] == "AND") {
        f[1][0] = 0,f[1][1] = 1;
    }else{
        f[1][0] = 1,f[1][1] = 2;
    }

    for(int i = 1; i < n; i++){
        if(vc[i] == "AND") {
            f[i+1][0] = 0;
            f[i+1][1] = f[i][1] + f[i][0];
        }else{
            f[i+1][0] = f[i][1] + f[i][0];
//          cout << f[i][1] <<" " << f[i][0] << endl;
            f[i+1][1] = 1LL << (i+1);
//          cout <<f[i+1][0]<<" " << f[i+1][1] <<endl;
        }
    }
    cout << f[n][1] + f[n][0];
} 

思路2（递归，因为这个可以写出一个递推公式）

其实思路和思路1一样，用f(n)表示n逻辑表达式计数为1的结果
当最后一位为OR时 f(n) = f(n-1) + 1ll << n;
否则 f(n) = f(n-1)

参考代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans;
vector<string> vc;
int f(int n ){
    if(n == 0 ){
        return 1;
    }

    if(vc[n] == "OR") return (1ll << n) + f(n-1);
    else return f(n-1);
}
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("tpl.txt","r",stdin);
    #endif
    vc.push_back("#");
    int n ; cin >> n;
    for(int i = 0 ; i < n ; i++) {
        string data; cin >> data;
        vc.push_back(data);
    }
    cout << f(n);
}