9/13/25, 4:11 AM Problem - F - Codeforces
Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 1045 (Div. 2)
F. Permutation Oddness Finished
time limit per test: 5 seconds
memory limit per test: 256 megabytes → Practice?
You are given four positive integers c0 , c1 , c2 , and c3 . Want to solve the contest problems after the
official contest ends? Just register for
practice and you will be able to submit
Let n = c0 + c1 + c2 + c3 . Consider an array a of n integers with x (0 ≤ x ≤ 3 ) appearing solutions.
cx times. For any distinct permutation b of the array a , define its oddness as :
∗ †‡
Register for practice
n−1
∑ lowbit(bi ⊕ bi+1 )
→ Virtual participation
i=1
Your task is to count, for each integer k from 0 to 2 ⋅ (n − 1) (inclusive), the number of distinct
Virtual contest is a way to take part in past
permutations of a with an oddness equal to k . contest, as close as possible to participation
on time. It is supported only ICPC mode for
virtual contests. If you've seen these
Since the numbers might be too large, you are only required to find them modulo 10
9
+ 7 . problems, a virtual contest is not for you -
solve these problems in the archive. If you
∗
A permutation of the array is an arrangement of its elements into any order. For example, [1, 2, 2] is a just want to solve some problem from a
permutation of [2, 2, 1], but [1, 1, 2] is not. Two permutations are considered distinct if they differ in at least one contest, a virtual contest is not for you -
solve this problem in the archive. Never use
position. someone else's code, read the tutorials or
†
⊕ denotes the bitwise XOR operation. communicate with other person during a
virtual contest.
‡
is the value of the lowest binary bit of x, e.g. lowbit(12)
lowbit(x) ,
= 4 lowbit(8) = 8 . Specifically, we
define lowbit(0) = 0 . Start virtual contest
Input
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 50 ). The description of the test cases follows. → Problem tags
The first and the only line of each test case contains four positive integers c0 , c1 , c2 , and c3 ( combinatorics dp math *2900
1 ≤ c0 , c1 , c2 , c3 < 800, 4 ≤ c0 + c1 + c2 + c3 ≤ 800 ). No tag edit access
Let n = c0 + c1 + c2 + c3 . It is guaranteed that the sum of n over all test cases does not
exceed 800. → Contest materials
Output Announcement (en)
For each test case, output 2 ⋅ (n − 1) + 1 integers in one line — the number of distinct
Tutorial (en)
permutations of a with an oddness equal to 0, 1, … , 2 ⋅ (n − 1) respectively. Output the
answers modulo 10
9
+ 7 .
Example
input Copy
3
1 1 1 1
1 2 4 1
3 3 3 3
output Copy
0 0 0 8 8 8 0
0 0 0 8 32 126 184 244 156 72 18 0 0 0 0
0 0 0 8 56 424 1472 5760 12128 29376 40384 65232 59920 65232 40384 29376 12128 5760
1472 424 56 8 0
Note
In the first test case, the array a has 24 distinct permutations. The table below shows the
oddness values for some selected permutations:
Permutation Oddness
[0, 1, 2, 3] lowbit(0 ⊕ 1) + lowbit(1 ⊕ 2) + lowbit(2 ⊕ 3) = 1 + 1 + 1 = 3
[0, 2, 1, 3] lowbit(0 ⊕ 2) + lowbit(2 ⊕ 1) + lowbit(1 ⊕ 3) = 2 + 1 + 2 = 5
[0, 1, 3, 2] lowbit(0 ⊕ 1) + lowbit(1 ⊕ 3) + lowbit(3 ⊕ 2) = 1 + 2 + 1 = 4
Overall, among the 24 permutations:
https://codeforces.com/contest/2134/problem/F 1/2
9/13/25, 4:11 AM Problem - F - Codeforces
8 permutations have oddness 3.
8 permutations have oddness 4.
8 permutations have oddness 5.
In the second test case, the array a has 840 distinct permutations. The distribution of oddness
values is as follows:
8permutations have oddness 3.
32 permutations have oddness 4.
126 permutations have oddness 5.
184 permutations have oddness 6.
244 permutations have oddness 7.
156 permutations have oddness 8.
72 permutations have oddness 9.
18 permutations have oddness 10 .
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/13/2025 04:11:08UTC+5.5 (k2).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
https://codeforces.com/contest/2134/problem/F 2/2
