fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <map>
  5. #include <sstream>
  6. #pragma GCC optimize(2)
  7. typedef long long ll;
  8. using namespace std;
  9. const int Mod = 1e9 + 7;
  10. struct Node {
  11.     Node* left;
  12.     Node* right;
  13.     string item;
  14.     Node() : left(nullptr), right(nullptr), item("") {}
  15. };
  16. bool isOp(string s) {
  17.     return (s == "*") || (s == "-") || (s == "+");
  18. }
  19. void dfs(Node* root, vector<string>& items, int& cnt) {
  20.     if (cnt < 0) {
  21.         return;
  22.     }
  23.     string tmp = items[cnt];
  24.     root -> item = tmp;
  25.     cnt--;
  26.     if (!isOp(tmp)) {
  27.         return;
  28.     }
  29.     root->left = new Node(); root->right = new Node();
  30.     dfs(root->right, items, cnt);
  31.     dfs(root->left, items, cnt);
  32. }
  33. Node* build(vector<string> items) {
  34.     Node* root = new Node();
  35.     int cnt = items.size()-1;
  36.     dfs(root, items, cnt);
  37.     return root;
  38. }
  39. ll cal(Node* root, map<string, ll>& value) {
  40.     if (root->item == "*") {
  41.         return (cal(root->left, value)%Mod * cal(root->right, value)%Mod)%Mod;
  42.     } else if (root->item == "-") {
  43.         return (cal(root->left, value)%Mod - cal(root->right, value)%Mod)%Mod;
  44.     } else if (root->item == "+") {
  45.         return (cal(root->left, value)%Mod + cal(root->right, value)%Mod)%Mod;
  46.     } else if (root->item[0] == 'x') {
  47.         return value[root->item]%Mod;
  48.     } else {
  49.         return stoi(root->item)%Mod;
  50.     }
  51.     return 0;
  52. }
  53. ll p_cal(Node* root, map<string, ll>& p_value, map<string, ll>& value) {
  54.     if (root->item == "*") {
  55.         return (p_cal(root->left, p_value, value)%Mod * cal(root->right, value)%Mod +
  56.         p_cal(root->right, p_value, value)%Mod * cal(root->left, value)%Mod)%Mod;
  57.     } else if (root->item == "-") {
  58.         return (p_cal(root->left, p_value, value)%Mod - p_cal(root->right, p_value, value)%Mod)%Mod;
  59.     } else if (root->item == "+") {
  60.         return (p_cal(root->left, p_value, value)%Mod + p_cal(root->right, p_value, value)%Mod)%Mod;
  61.     } else if (root->item[0] == 'x') {
  62.         return p_value[root->item]%Mod;
  63.     } else {
  64.         return 0;
  65.     }
  66.     return 0;
  67. }
  68. int main () {
  69.     int n, m; cin >> n >> m; getchar();
  70.     string line, token;
  71.     getline(cin, line);
  72.     istringstream iss(line);
  73.     vector<string> items;
  74.     while (iss >> token) items.push_back(token);
  75.     Node* root = build(items);
  76.     for (int i = 0; i < m; ++i) {
  77.         int x; cin >> x;
  78.         map<string, ll> value;
  79.         map<string, ll> p_value;
  80.         for (int i = 1; i <= n; ++i) {
  81.             string str = "x" + to_string(i);
  82.             int val; cin >> val;
  83.             value[str] = val;
  84.             if (i == x) p_value[str] = 1;
  85.             else p_value[str] = 0;
  86.         }
  87.         cout << (p_cal(root, p_value, value) + Mod)%Mod << endl;
  88.     }
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
60 1
x1 x2 + x3 x4 + * x5 x6 + * x7 x8 + * x9 x10 + * x11 x12 + * x13 x14 + * x15 x16 + * x17 x18 + * x19 x20 + * x21 x22 + * x23 x24 + * x25 x26 + * x27 x28 + * x29 x30 + * x31 x32 + * x33 x34 + * x35 x36 + * x37 x38 + * x39 x40 + * x41 x42 + * x43 x44 + * x45 x46 + * x47 x48 + * x49 x50 + * x51 x52 + * x53 x54 + * x55 x56 + * x57 x58 + * x59 x60 + * 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
stdout 
0
https://ideone.com/MBlPAs
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!