G. Count Mix Strings

Codeforces

IDCF10088G

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

While I was working in the company, the internet broke. I didn't have anything to do without internet, so I decided to write this ACM problem. We need to mix between two strings and also we should keep the same order for both strings. example: if we have s1 = "ab" and s2 = "cd", we can generate six strings: abcd acbd acdb cdab cadb cabd but now I have a problem. I need to calculate the complexity for this problem to make input and output files. you will be given the length of two strings and you should help me to find the number of strings that could be generated (if there is a repeated string, count it every time). Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 10000). Followed by the test cases, each test case is on one line. it contains two numbers N and M the length of s1 and s2 where 1 ≤ N, M ≤ 10000 For each test case, print a single line which contains a single integer that is representing the number of strings that could be generated MOD 10^9+7. ## Input Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 10000). Followed by the test cases, each test case is on one line. it contains two numbers N and M the length of s1 and s2 where 1 ≤ N, M ≤ 10000 ## Output For each test case, print a single line which contains a single integer that is representing the number of strings that could be generated MOD 10^9+7. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of gift packs. For each pack $ i \in \{1, \dots, N\} $, define: - $ x_i \in [L_i, R_i] \cap \mathbb{Z} $, - $ y_i \in [0, A_i] \cap \mathbb{Z} $, - $ z_i \in [0, B_i] \cap \mathbb{Z} $. **Objective** For each pack $ i $, maximize: $$ f(x_i, y_i, z_i) = (x_i \oplus y_i) \& z_i $$ **Constraints** For each $ i \in \{1, \dots, N\} $: - $ 0 \le L_i \le R_i \le 10^{18} $ - $ 0 \le A_i, B_i \le 10^{18} $ **Output** For each $ i $, output $ \max_{x_i \in [L_i,R_i],\, y_i \in [0,A_i],\, z_i \in [0,B_i]} \left( (x_i \oplus y_i) \& z_i \right) $.

API Response (JSON)

{
  "problem": {
    "name": "G. Count Mix Strings",
    "description": {
      "content": "While I was working in the company, the internet broke. I didn't have anything to do without internet, so I decided to write this ACM problem.  We need to mix between two strings and also we should k",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10088G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "While I was working in the company, the internet broke. I didn't have anything to do without internet, so I decided to write this ACM problem. \n\nWe need to mix between two strings and also we should k...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of gift packs.  \nFor each pack $ i \\in \\{1, \\dots, N\\} $, define:  \n- $ x_i \\in [L_i, R_i] \\cap \\mathbb{Z} $,  \n- $ y_i \\in [0, A_i] \\cap \\ma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments