表达式组成方案_

C/C++

nbgao

class Expression {     string str;     int DP[333][333][2];     int n;     int MOD;     void dp()     {         for(int l=0;l<n;l+=2)         {             for(int i=0;i+l<n;i+=2)             {                 int v[2] = {0,0};                 if(l==0)                 {                     int c = str[i] - '0';                     DP[i][i+l][c] = 1;                     DP[i][i+l][c^1] = 0;                     continue;                 }                 for(int j=i;j<i+l;j+=2)                 {                     int t[3] = {                         (DP[i][j][0]%MOD)*(DP[j+2][i+l][0]%MOD),                         (DP[i][j][0]%MOD)*(DP[j+2][i+l][1]%MOD)+(DP[i][j][1]%MOD)*(DP[j+2][i+l][0]%MOD),                         (DP[i][j][1]%MOD)*(DP[j+2][i+l][1]%MOD)                     };                     t[0] %= MOD;                     t[1] %= MOD;                     t[2] %= MOD;                     switch (str[j+1])                     {                         case '|':                             v[0] += t[0];                             v[1] += t[1] + t[2];                             break;                         case '&':                             v[0] += t[0] + t[1];                             v[1] += t[2];                             break;                         case '^':                             v[0] += t[0] + t[2];                             v[1] += t[1];                             break;                     }                     v[0] %= MOD;                     v[1] %= MOD;                 }                 DP[i][i+l][0] = v[0];                 DP[i][i+l][1] = v[1];             }         }     }
public:
    int countWays(string exp, int len, int ret) {
        str = exp;
        n = len;
        MOD = 1e4+7;         dp();         return DP[0][n-1][ret];
    }
};

发表于 2017-12-27 03:26:27 回复(0)

Alex-大伟

//参考的JustYoung大神  import java.util.Scanner;

public class test7 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int len = scanner.nextInt();
			String exp = scanner.next();
			int ret = scanner.nextInt();
			System.out.println(countWays(exp, len, ret));
		}
	}

	// 三维dp矩阵 dp[i][j][z],表示从i到j计算结果为z的所有方法总和，这里z的取值只有0和1两种。
	// 构造dp[i][j][z]的方法是对dp[i][k][z]*dp[k+1][j][z]求和，k取值范围从i到j-1
	public static int countNum(int[] nums, char[] ops, int ret) {
		int n = nums.length;
		int[][][] d = new int[n][n][2];
		for (int i = 0; i < n; i++) {
			if (nums[i] == 1) {
				d[i][i][1] = 1;
			} else {
				d[i][i][0] = 1;
			}
		}
		for (int x = 1; x < n; x++) { // 外循环是各个数字位
			for (int i = 0; i < n - x; i++) {
				int j = i + x;
				for (int k = i; k < j; k++) {
					if (d[i][k][0] != 0 && d[k + 1][j][0] != 0) {
						int num = cal(0, 0, ops[k]);
						d[i][j][num] = (d[i][j][num] + d[i][k][0] * d[k + 1][j][0]) % 10007;
					}
					if (d[i][k][0] != 0 && d[k + 1][j][1] != 0) {
						int num = cal(0, 1, ops[k]);
						d[i][j][num] = (d[i][j][num] + d[i][k][0] * d[k + 1][j][1]) % 10007;
					}
					if (d[i][k][1] != 0 && d[k + 1][j][0] != 0) {
						int num = cal(1, 0, ops[k]);
						d[i][j][num] = (d[i][j][num] + d[i][k][1] * d[k + 1][j][0]) % 10007;
					}
					if (d[i][k][1] != 0 && d[k + 1][j][1] != 0) {
						int num = cal(1, 1, ops[k]);
						d[i][j][num] = (d[i][j][num] + d[i][k][1] * d[k + 1][j][1]) % 10007;
					}
				}
			}
		}
		return d[0][n - 1][ret];
	}

	public static int countWays(String exp, int len, int ret) {
		char[] cs = exp.toCharArray();
		int[] nums = new int[(len + 1) / 2]; // 存放数字位
		char[] ops = new char[(len - 1) / 2]; // 存放操作符位
		for (int i = 0; i < len; i++) {
			if (i % 2 == 0) {
				nums[i / 2] = Integer.valueOf(cs[i] - '0');
			} else {
				ops[i / 2] = cs[i];
			}
		}
		return countNum(nums, ops, ret) % 10007;
	}

	public static int cal(int a, int b, char op) {
		if (op == '^') {
			return a ^ b;
		} else if (op == '|') {
			return a | b;
		} else {
			return a & b;
		}
	}
}

编辑于 2016-10-08 22:22:53 回复(0)

VOODOO

/**
可以运用区间DP的思想
对于一个区间[L,R]来说 我们把它以K为中点分为两份

设该表达式为最后算的一个表达式
也就是现在要算的表达式为[L,k][k+1,k+1][k+2,R]有多少种方案为ret。

先讨论符号  例如exp[k-1]='^'
那么我们有真值表
[L,k]	[k+2,R]	[L,R]
0	0	0
0	1	1
1	0	1
1	1	0

那么[L,R]中 0的方案数=[L,k]中0的方案数*[k+2,R]中0的方案数+[L,k]中1的方案数*[k+2,R]中1的方案数
这样我们就能求出[L,R]的以K分组的方案数了
注意  我这里说的是以K分组
那求[L,R]的方案数就是分别以L,L+2...R-2分组的方案数之和
这就是区间DP的思想
其他运算符以此类推
*/

class Expression {
    string str;
    int DP[333][333][2];
    int n;
    int MOD;
///这里DP采用打表的方法
///其实也可用记忆化搜索  可以理解理解区间DP
    void dp()
    {
        ///枚举长度
        for(int len=0;len<n;len+=2)
            ///枚举起始点
            for(int i=0;i+len<n;i+=2)
            {
                ///v是当前区间ret=0 的和 与 ret=1 的和
                int v[2]={0,0};
                ///len==0时说明现在区间为[i,i] 应初始化为str的值
                if(len==0)
                {

                    int c=str[i]-'0';
                    DP[i][i+len][c]=1;
                    DP[i][i+len][c^1]=0;
                    continue;
                }
                ///j为枚举k点
                for(int j=i;j<i+len;j+=2)
                {
                    ///t为真值表中左右两个区间对应的方案数
                    ///t[0]为    0   0
                    ///t[1]为    0   1   *   0   1
                    ///t[2]为    1   1
                    int t[3]=
                    {
                        (DP[i][j][0]%MOD)*(DP[j+2][i+len][0]%MOD),
                        (DP[i][j][0]%MOD)*(DP[j+2][i+len][1]%MOD)+(DP[i][j][1]%MOD)*(DP[j+2][i+len][0]%MOD),
                        (DP[i][j][1]%MOD)*(DP[j+2][i+len][1]%MOD)
                    };
                    t[0]%=MOD;
                    t[1]%=MOD;
                    t[2]%=MOD;
                    ///处理运算符
                    switch (str[j+1])
                    {
                        case '|':
                            v[0]+=t[0];
                            v[1]+=t[1]+t[2];
                            break;
                        case '&':
                            v[0]+=t[0]+t[1];
                            v[1]+=t[2];
                            break;
                        case '^':
                            v[0]+=t[0]+t[2];
                            v[1]+=t[1];
                            break;
                    }
                    v[0]%=MOD;
                    v[1]%=MOD;
                }
                ///为区间赋值
                DP[i][i+len][0]=v[0];
                DP[i][i+len][1]=v[1];
            }
    }
public:
    int countWays(string exp, int len, int ret)
    {
        str=exp;
        n=len;
        MOD=1e4+7;
        dp();
        return DP[0][n-1][ret];
        // write code here
    }
};

发表于 2015-08-19 21:40:51 回复(2)

Java

JustYoung

这题切记要对每一步计算加上取余数的操作 % 10007，否则过不了。

思路：构造三维dp矩阵 dp[i][j][z]，表示从i到j计算结果为z的所有方法总和，这里z的取值只有0和1两种。构造dp[i][j][z]的方法为对dp[i][k][z]*dp[k+1][j][z]求和，k取值范围从i到j-1。从矩阵的对角线开始，向右上方计算，和矩阵连乘求乘法次数最少的加括号方式类似。

import java.util.*;

public class Expression {
    public int cal(int d1, int d2, char op) {

        if (op == '&') {
            return d1 & d2;
        } else if (op == '|') {
            return d1 | d2;
        } else {
            return d1 ^ d2;
        }
    }

    public int count(int[] digits, char[] ops, int des) {

        int n = digits.length;

        int[][][] dp = new int[n][n][2];

        for (int i = 0; i < n; ++i) {
            if (digits[i] == 1) {
                ++dp[i][i][1];
            } else {
                ++dp[i][i][0];
            }
        }

        for (int x = 1; x < digits.length; ++x) {
            for (int i = 0; i < digits.length - x; ++i) {
                int j = i + 1 + x - 1;
                for (int k = i; k < j; ++k) {
                    if (dp[i][k][0] != 0 && dp[k + 1][j][0] != 0) {
                        int num = cal(0, 0, ops[k]);
                        dp[i][j][num] = (dp[i][j][num] + dp[i][k][0] * dp[k + 1][j][0]) % 10007;
                    }
                    if (dp[i][k][0] != 0 && dp[k + 1][j][1] != 0) {
                        int num = cal(0, 1, ops[k]);
                        dp[i][j][num] = (dp[i][j][num] + dp[i][k][0] * dp[k + 1][j][1]) % 10007;
                    }
                    if (dp[i][k][1] != 0 && dp[k + 1][j][0] != 0) {
                        int num = cal(1, 0, ops[k]);
                        dp[i][j][num] = (dp[i][j][num] + dp[i][k][1] * dp[k + 1][j][0]) % 10007;
                    }
                    if (dp[i][k][1] != 0 && dp[k + 1][j][1] != 0) {
                        int num = cal(1, 1, ops[k]);
                        dp[i][j][num] = (dp[i][j][num] + dp[i][k][1] * dp[k + 1][j][1]) % 10007;
                    }
                }
            }
        }

        return dp[0][n - 1][des];
    }

    public int countWays(String exp, int len, int ret) {
        // write code here
        char[] exps = exp.toCharArray();
        int[] digits = new int[(exps.length + 1) / 2];
        char[] ops = new char[(exps.length - 1) / 2];
        for (int i = 0; i < exps.length; ++i) {
            if (i % 2 == 0) {
                digits[i / 2] = Integer.valueOf(exps[i] - '0');
            } else {
                ops[i / 2] = exps[i];
            }
        }
        return count(digits, ops, ret) % 10007;
    }
}

发表于 2016-08-30 19:26:03 回复(4)

皮蛋秀柚秋

class Expression {
public:
    bool isValid(string exp,int len)
    {
        if(len%2==0) return false;
        for(int i=0;i<len;++i)
        {
            if(i%2==0)
            {
                if(exp[i]!='0'&&exp[i]!='1') return false;
            }
            else{
                if(exp[i]!='^'&&exp[i]!='|'&&exp[i]!='&')return false;
            }
            
        }
        return true;
    }
    int countWays(string exp, int len, int ret) {
        // write code here
        int mod = 1e4+7;
        if(!isValid(exp,len)) return 0;
        vector<vector<long long >>t(len,vector<long long>(len));
        vector<vector<long long>>f(len,vector<long long>(len));
        t[0][0] = exp[0]== '0' ? 0 : 1;
        f[0][0] = exp[0]== '0' ? 1 : 0;
        for(int i=2;i<len;i+=2)
        {
            t[i][i] = exp[i] == '0' ? 0 : 1;
            f[i][i] = exp[i] == '0' ? 1 : 0;
            for(int j=i-2;j>=0;j-=2)
                for(int k=j;k<i;k+=2)
                {
                    if(exp[k+1]=='&')
                    {
                        t[j][i] += (t[j][k]*t[k+2][i])%mod;
                        f[j][i] += (t[j][k]*f[k+2][i]+f[j][k]*f[k+2][i]+f[j][k]*t[k+2][i])%mod;
                    }
                    else if(exp[k+1]=='|')
                    {
                        t[j][i] += (t[j][k]*(f[k+2][i]+t[k+2][i])+ f[j][k]*t[k+2][i])%mod;
                        f[j][i] += (f[j][k]*f[k+2][i])%mod;
                    }
                    else{
                        t[j][i] += (t[j][k]*f[k+2][i]+f[j][k]*t[k+2][i])%mod;
                        f[j][i] += (t[j][k]*t[k+2][i]+f[j][k]*f[k+2][i])%mod;
                    }
                }
           
        }
         return ret ? (t[0][len-1]%mod):(f[0][len-1]%mod);
        
    }
};

发表于 2020-04-29 17:06:16 回复(0)

C/C++

🐻Leeee🐻

class Expression {
public:
    int bit(int left,char op,int right){
        if(op=='|') return left|right;
        if(op=='^') return left^right;
        return left&right;
    }
    int countWays(string exp, int len, int ret) {
        int n=len/2+1;
        //dp[i][j][k]表示从i到j结果为k的方案数
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(2,0)));
        string num="",op="";//需要先把数字和运算符分开
        for(int i=0;i<len;++i)
            if(i%2) op+=exp[i];
            else num+=exp[i];

        //初值
        for(int i=0;i<n;++i)
            dp[i][i][num[i]-'0']=1;

        for(int length=1;length<n;++length)//长度
            for(int left=0;left<n-length;++left){//左端点
                int right=left+length;//右端点
                for(int mid=left;mid<right;++mid)//加括号的方法可以为(left-mid) op (mid+1,right)，方案数为二者相乘
                    for(int i=0;i<=1;++i)//枚举0，1
                        for(int j=0;j<=1;++j){//枚举0，1
                            int k=bit(i,op[mid],j);//k为 i op j 结果
                            //left-right结果为k的方案数为 left---mid 结果为 i 的方案数乘以 mid+1---right 结果为 j 的方案数相乘
                            dp[left][right][k]=(dp[left][right][k]+dp[left][mid][i]*dp[mid+1][right][j]) % 10007;
                    }
            }

        return dp[0][n-1][ret];

    }
};

发表于 2019-03-17 20:41:26 回复(0)

fFarther

#include<iostream>
#include<vector>
using namespace std;
#define M 10007
#define N 301
/*
    for(k=i;k<=j;k+=2){
        if(i==j){
            ret[i][j][1]=(exp[i]=='1'?1:0);
            ret[i][j][0]=(exp[i]=='1'?0:1);
        }//if
        else{
            switch(exp[k+1]){
                case '|':
                    ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0])%M;
                    ret[i][j][1]+=(ret[i][k][0]*ret[k+2][j][1]+
                                  ret[i][k][1]*ret[k+2][j][0]+
                                  ret[i][k][1]*ret[k+2][j][1])%M;
                break;
                case '^':
                    ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0]+
                                  ret[i][k][1]*ret[k+2][j][1])%M;
                    ret[i][j][1]+=(ret[i][k][0]*ret[k+2][j][1]+
                                  ret[i][k][1]*ret[k+2][j][0])%M;
                break;
                case '&':
                    ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0]+
                                   ret[i][k][1]*ret[k+2][j][0]+
                                   ret[i][k][0]*ret[k+2][j][1])%M;
                    ret[i][j][1]+=(ret[i][k][1]*ret[k+2][j][1])%M;
                break;
            }//switch
        }//else
    }//for
*/
int fun1(string exp, int len, int ret){
    int result[N][N][2];
    int inc=0,i=0,k=0,j=0;
    for(inc=0;inc<len;inc+=2){
        for(i=0;i<len;i+=2){
            j=i+inc;
            for(k=i;k<=j;k+=2){
        if(i==j){
            result[i][j][1]=(exp[i]=='1'?1:0);
            result[i][j][0]=(exp[i]=='1'?0:1);
        }//if
        else{
            switch(exp[k+1]){
                case '|':
                    result[i][j][0]+=(result[i][k][0]*result[k+2][j][0])%M;
                    result[i][j][1]+=(result[i][k][0]*result[k+2][j][1]+
                                  result[i][k][1]*result[k+2][j][0]+
                                  result[i][k][1]*result[k+2][j][1])%M;
                break;
                case '^':
                    result[i][j][0]+=(result[i][k][0]*result[k+2][j][0]+
                                  result[i][k][1]*result[k+2][j][1])%M;
                    result[i][j][1]+=(result[i][k][0]*result[k+2][j][1]+
                                  result[i][k][1]*result[k+2][j][0])%M;
                break;
                case '&':
                    result[i][j][0]+=(result[i][k][0]*result[k+2][j][0]+
                                   result[i][k][1]*result[k+2][j][0]+
                                   result[i][k][0]*result[k+2][j][1])%M;
                    result[i][j][1]+=(result[i][k][1]*result[k+2][j][1])%M;
                break;
            }//switch
        }//else
    }//for
        }//start
    }//increment
    return result[0][len-1][ret];
}
int main(){
    int n=0;
    string A="0|0|0";
    cout<<fun1(A,5,0)<<endl;
    return 0;
}

发表于 2017-07-10 14:02:53 回复(0)

wyg_031113

//可以动态规划
//经典类型：
//0-0 1-1 2-2 3-3  步长为1
//0-1 1-2 2-3      步长为2
//0-2 1-3          步长为3
//0-3              步长为4
//可以先把数字和运算符分别放在A和B中
//dp[i][j][0]   i~j中能形成0的有多少种
//dp[i][j][1] i~j中能形成1的有多少种
//0<=a,b<=1   OP=&,|,^
//dp[i][j][a OP b] += (dp[i][k][a] * dp[k + 1][j][b]) % MOD;  
// i<=k<j;   0<=i,j<=A.size();  OP = B[k] #include <iostream>
#include <string>
#include <cstring>
using namespace std;
class Expression {
public:
	const int MOD = 10007;
    int dp[151][151][2];
    int ec(int a, int b, char op){
        switch(op){
            case '&':
                return a && b;
            case '|':
                return a || b;
            case '^':
                return ( (a ^ b) != 0);
            throw "bad op";
        }
        return 0;
    }
    void calc(int i, int j, int k, char op)
    {
        for(int a = 0; a < 2; a++)
            for(int b = 0; b < 2; b++){
                int c = ec(a,b,op);
                dp[i][j][c] += (dp[i][k][a] * dp[k + 1][j][b]) % MOD;
                dp[i][j][c] %= MOD;
            }
    }
	int countWays(string exp, int len, int ret) {
		// write code here
		
		memset(dp, 0, sizeof(dp));
		string A;
		string B;
		for (int i = 0; i < len; i++) {
			if (i & 1) {
				B += exp.substr(i, 1);
			}
			else {
				A += exp.substr(i, 1);
			}
		}
		for (int i = 0; i < A.size(); i++)
			for (int k = 0; k < 2; k++)
				dp[i][i][k] = ((A[i] - '0') == k);

		for (int step = 2; step <= A.size(); step++) {
			for (int i = 0; i < A.size(); i++) {
				int j = i + step - 1;
				if (j >= A.size())
					break;
				for (int k = i; k < j; k++) {
                    calc(i,j,k, B[k]);
				}
			}
		}
		return dp[0][A.size() - 1][ret];
	}
};

#ifdef LOCAL
int main()
{
	Expression exp;
	cout << exp.countWays("1^0|0|1", 7, 0) << endl;
}
#endif

发表于 2017-05-21 10:20:48 回复(0)

Java

Holiday_12138

public static int countWays(String exp, int len, int ret) {
        int n=len/2+1;
        int[][][] dp=new int[n][n][2];//dp[l][r][p],从l到r范围，可以得到p结果的个数
        char[] op=new char[n-1];
        int[] num=new int[n];
        for(int i=0;i<len-1;i+=2){
            num[i/2]=exp.charAt(i)-'0';
            op[i/2]=exp.charAt(i+1);
        }
        num[n-1]=exp.charAt(len-1)-'0';
        for(int l=0;l<n;l++){
            for(int i=0;i+l<n;i++){
                if(l==0){
                    dp[i][i][num[i]]=1;
                    dp[i][i][num[i]^1]=0;
                }
                else{
                    int n0=0,n1=0;
                    for(int j=i;j<i+l;j++){
                        int p00,p01,p11;
                        p00=(dp[i][j][0]%10007)*(dp[j+1][i+l][0]%10007)%10007;
                        p01=(dp[i][j][0]%10007)*(dp[j+1][i+l][1]%10007)%10007+(dp[i][j][1]%10007)*(dp[j+1][i+l][0]%10007)%10007;
                        p11=(dp[i][j][1]%10007)*(dp[j+1][i+l][1]%10007)%10007;
                        switch(op[j]){
                        case '|':
                            n0+=p00;
                            n1+=p01+p11;
                            break;
                        case '&':
                            n0+=p00+p01;
                            n1+=p11;
                            break;
                        case '^':
                            n0+=p00+p11;
                            n1+=p01;
                            break;
                        }
                    }
                    n0%=10007;
                    n1%=10007;
                    dp[i][i+l][0]=n0;
                    dp[i][i+l][1]=n1;
                }
            }
        }
        return dp[0][n-1][ret];
    }

发表于 2017-03-21 13:33:31 回复(0)

GOFORW

//哈哈，使用区间dp的算法，终于还是通过了，虽然参考了网上的其他代码

//

// Created by Qiu on 2016-11-21.

//

#include <iostream>

#include <cstring>

using namespace std;

class Expression {

public:

int countWays(string exp, int len, int ret) {

// write code here

int mod = 1e4 + 7;

int dp[len][len][2];

memset(dp, 0, len * len * 2 * sizeof(int));

//区间长度

for (int s = 0; s < len; s += 2) {

//开始枚举的起点

for (int i = 0; i + s < len; i += 2) {

int v[2] = { 0, 0 };

if (s == 0) {

int c = exp[i] - '0';

dp[i][i][c] = 1;

dp[i][i][c^1] = 0;

//真是***啊，这里不加continue怎么可以啊

continue;

}

//j表示的是中间的分界点

for (int j = i; j < i + s; j += 2) {

int t[3] = {

(dp[i][j][0] % mod) * (dp[j+2][i+s][0] % mod),

(dp[i][j][0] % mod) * (dp[j+2][i+s][1] % mod) + (dp[i][j][1] % mod) * (dp[j+2][i+s][0] % mod),

(dp[i][j][1] % mod) * (dp[j+2][i+s][1] % mod)

};

t[0] %= mod;

t[1] %= mod;

t[2] %= mod;

switch(exp[j+1]) {

case '|':

v[0] += t[0];

v[1] += t[1] + t[2];

break;

case '&':

v[0] += t[0] + t[1];

v[1] += t[2];

break;

case '^':

v[0] += t[0] + t[2];

v[1] += t[1];

break;

default:

break;

}

v[0] %= mod;

v[1] %= mod;

}

dp[i][i+s][0] = v[0];

dp[i][i+s][1] = v[1];

}

return dp[0][len-1][ret];

}

};

int main() {

string exp = "1^0|0|1";

Expression ex;

cout << ex.countWays(exp, 7, 0);

return 0;

}//

// Created by Qiu on 2016-11-21.

//

#include <iostream>

#include <cstring>

using namespace std;

class Expression {

public:

int countWays(string exp, int len, int ret) {

// write code here

int mod = 1e4 + 7;

int dp[len][len][2];

memset(dp, 0, len * len * 2 * sizeof(int));

//区间长度

for (int s = 0; s < len; s += 2) {

//开始枚举的起点

for (int i = 0; i + s < len; i += 2) {

int v[2] = { 0, 0 };

if (s == 0) {

int c = exp[i] - '0';

dp[i][i][c] = 1;

dp[i][i][c^1] = 0;

//真是***啊，这里不加continue怎么可以啊

continue;

}

//j表示的是中间的分界点

for (int j = i; j < i + s; j += 2) {

int t[3] = {

(dp[i][j][0] % mod) * (dp[j+2][i+s][0] % mod),

(dp[i][j][0] % mod) * (dp[j+2][i+s][1] % mod) + (dp[i][j][1] % mod) * (dp[j+2][i+s][0] % mod),

(dp[i][j][1] % mod) * (dp[j+2][i+s][1] % mod)

};

t[0] %= mod;

t[1] %= mod;

t[2] %= mod;

switch(exp[j+1]) {

case '|':

v[0] += t[0];

v[1] += t[1] + t[2];

break;

case '&':

v[0] += t[0] + t[1];

v[1] += t[2];

break;

case '^':

v[0] += t[0] + t[2];

v[1] += t[1];

break;

default:

break;

}

v[0] %= mod;

v[1] %= mod;

}

dp[i][i+s][0] = v[0];

dp[i][i+s][1] = v[1];

}

return dp[0][len-1][ret];

}

};

int main() {

string exp = "1^0|0|1";

Expression ex;

cout << ex.countWays(exp, 7, 0);

return 0;

}

发表于 2016-11-21 19:55:35 回复(0)

senji

import java.util.*;

public class Expression {
    public int countWays(String exp, int len, int ret) {
        // write code here
        int[][][] dp = new int[len][len][2];
        final int MOD = 10007;
        //枚举长度
        for(int l=0; l<len; l+=2){
            //枚举起点
            for(int i=0; i+l<len; i+=2){
                int[] v = {0,0};
                if(l==0){
                    int c = exp.charAt(i) - '0';
                    dp[i][i][c] = 1;
                    dp[i][i][c^1] = 0;
                }
                else{
                    //枚举中点
                    for(int j=i; j<i+l; j+=2){
                        int[] t = new int[3];
                        t[0] = ((dp[i][j][0]%MOD)*(dp[j+2][i+l][0]%MOD))%MOD;
                        t[1] = ((dp[i][j][1]%MOD)*(dp[j+2][i+l][0]%MOD) + (dp[i][j][0]%MOD)*(dp[j+2][i+l][1]%MOD))%MOD;
                        t[2] = ((dp[i][j][1]%MOD)*(dp[j+2][i+l][1]%MOD))%MOD;
                        char c = exp.charAt(j+1);
                        if(c == '&'){
                            v[0] += t[0] + t[1];
                            v[1] += t[2];
                        }else if(c == '|'){
                            v[0] += t[0];
                            v[1] += t[1] + t[2];
                        }else if(c == '^'){
                            v[0] += t[0] + t[2];
                            v[1] += t[1];
                        }
                        v[0] %= MOD;
                        v[1] %= MOD;
                    }
                    dp[i][i+l][0] = v[0];
                    dp[i][i+l][1] = v[1];
                }
            }
        }
        return dp[0][len-1][ret];
    }
}

发表于 2016-04-15 16:30:40 回复(0)

Paseam

class Expression

{

public:

int countWays(string exp, int len, int ret)

{

vector<vector<vector<long long>>> table(2, vector<vector<long long>>(len, vector<long long>(len, -1)));

int tmp= funCore(exp, 0, len - 1, ret,table);

return (tmp % 10007);

}

int funCore(string &exp, int beg, int end, int t, vector<vector<vector<long long>>> &table)

{

if (table[t][beg][end] !=-1)

return table[t][beg][end];

if (beg == end)

{

if (exp[beg] == '0' + t)

{

table[t][beg][beg] = 1;

return 1;

}

else

{

table[t][beg][beg] = 0;

return 0;

}

long long ret = 0;

for (int i = beg + 1; i <= end - 1; i += 2)

{

switch (exp[i])

{

case '|':

if (t == 1)

{

ret = ret + funCore(exp, beg, i - 1, 0, table)

* funCore(exp, i + 1, end, 1, table);

ret = ret + funCore(exp, beg, i - 1, 1, table)

* funCore(exp, i + 1, end, 0, table);

ret = ret + funCore(exp, beg, i - 1, 1, table)

* funCore(exp, i + 1, end, 1, table);

}

else

{

ret = ret + funCore(exp, beg, i - 1, 0, table)

* funCore(exp, i + 1, end, 0, table);

}

break;

case '&':

if (t == 0)

{

ret = ret + funCore(exp, beg, i - 1, 0, table)

* funCore(exp, i + 1, end, 1, table);

ret = ret + funCore(exp, beg, i - 1, 1, table)

* funCore(exp, i + 1, end, 0, table);

ret = ret + funCore(exp, beg, i - 1, 0, table)

* funCore(exp, i + 1, end, 0, table);

}

else

{

ret = ret + funCore(exp, beg, i - 1, 1, table)

* funCore(exp, i + 1, end, 1, table);

}

break;

case '^':

if (t == 1)

{

ret = ret + funCore(exp, beg, i - 1, 0, table)

* funCore(exp, i + 1, end, 1, table);

ret = ret + funCore(exp, beg, i - 1, 1, table)

* funCore(exp, i + 1, end, 0, table);

}

else

{

ret = ret + funCore(exp, beg, i - 1, 1, table)

* funCore(exp, i + 1, end, 1, table);

ret = ret + funCore(exp, beg, i - 1, 0, table)

* funCore(exp, i + 1, end, 0, table);

}

break;

}

table[t][beg][end] = ret % 10007;

return ret % 10007;

}

};

发表于 2015-08-07 16:33:14 回复(0)

表达式组成方案

问题信息

热门推荐

通过挑战的用户

相关试题