1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

int n, m;

int tab[100];
long long int sposoby[10003][43];

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", &tab[i]);

    /* m=n-(n/2); */
    /* n/=2; */
    for(int i=1; i<(1<<n); i++)
    {
        int zgrzyt=0, bity=0;
        for(int j=0; j<n; j++)
            if((1<<j)&i)
                bity++;

        for(int j=0; j<n; j++)
            if((1LL<<j)&i)
                for(int k=j+1; k<n; k++)
                    if((1<<k)&i)
                        if(tab[j]>tab[k])
                            zgrzyt++;
        sposoby[zgrzyt][bity]++;
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<100004; j++)
            if(sposoby[j][i]!=0)
            {
                printf("%d %lld\n", j, sposoby[j][i]);
                break;
            }
}