# P2159 [Show2009] dance (DP & high precision)

2021-08-10 08:45:10

P2159 [SHOI2009] ball (DP& Hyperfine )

n = 200 n=200 n=200, consider n 3 n^3 n3 Of d p dp dp, But there is no module in this question , So high precision , And the high precision constant is huge , So consider n 2 n^2 n2 Of d p dp dp.

Make f [ i ] [ j ] f[i][j] f[i][j] front i i i Yes, among men and women j j j The number of schemes for women is higher than that for men .

The answer is ： a n s = ∑ i = 0 k f [ n ] [ i ] \large ans=\sum\limits_{i=0}^k f[n][i] ans=i=0kf[n][i]

Consider how state transitions .

For the current i i i A man a i a_i ai And the i i i A woman Discussion by situation .

1 : a i ≥ b i \large 1:a_i\ge b_i 1:aibi

Then divide j j j Increase and no increase .

j j j Don't add ： First, let's count [ 1 , i ] [1,i] [1,i] How many men are there ≥ b i \ge b_i bi, We remember that c n t cnt cnt.

here c n t cnt cnt Include i i i, To bring f [ i − 1 ] [ j ] f[i-1][j] f[i1][j] Original contribution .

Obviously this c n t cnt cnt Yes, men were taller before , Because they all ≥ b i \ge b_i bi, So it must be greater than or equal to b k b_k bk.

So this c n t cnt cnt In one case j j j No increase . Another situation is from j j j In exchange , Because it turns out that women are taller , After exchanging the women in the corresponding positions , Or are women taller , And the first i i i Men are still higher than women .

So the contribution is ： f [ i ] [ j ] = f [ i − 1 ] [ j ] × ( j + c n t ) f[i][j]=f[i-1][j]\times (j+cnt) f[i][j]=f[i1][j]×(j+cnt)

then j j j The added contribution is ： The total number of i i i subtract j j j No increase in the number of people .

f [ i ] [ j ] = f [ i ] [ j ] + f [ i − 1 ] [ j − 1 ] × ( i − [ ( j − 1 ) + c n t ] ) f[i][j]=f[i][j]+f[i-1][j-1]\times (i-[(j-1)+cnt]) f[i][j]=f[i][j]+f[i1][j1]×(i[(j1)+cnt])

2. a i < b i \large 2.a_i<b_i 2.ai<bi

In the same way c n t cnt cnt To statistics [ 1 , i ) [1,i) [1,i) How many women are higher than b i b_i bi

Not included here i i i To bring f [ i − 1 ] [ j ] f[i-1][j] f[i1][j] Original contribution .

And then in women's higher j j j Subtract... From the alignment c n t cnt cnt, After the exchange, the woman is less than or equal to a i a_i ai Of , One plus one minus means no increase .

f [ i ] [ j ] = f [ i − 1 ] [ j ] × ( j − c n t ) f[i][j]=f[i-1][j]\times (j-cnt) f[i][j]=f[i1][j]×(jcnt)

Then add the case with i i i Just subtract .

f [ i ] [ j ] = ( f [ i ] [ j ] + f [ i − 1 ] [ j − 1 ] × ( i − ( j − 1 − c n t ) ) ) f[i][j]=(f[i][j]+f[i-1][j-1]\times (i-(j-1-cnt))) f[i][j]=(f[i][j]+f[i1][j1]×(i(j1cnt)))

The answer is big , High precision , Because they are all transferred from the previous state , Scrollable array .

Scroll the array. Note that each initialization is cleared .

// Problem: P2159 [SHOI2009] ball
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2159
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-07-23 09:31:24
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=205,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
struct num{
int len,c[M];
num(){}	//no parameter init
num(int x){ mst(c,0);//init by number
if(!x) len=1;
else{len=0;while(x) c[++len]=x%10,x/=10;}
}
num operator =(int x){
mst(c,0);
if(!x) len=1;
else{len=0;while(x) c[++len]=x%10,x/=10;}
return *this;
}
num operator +(const num &b)const{	// High precision additive
num ans(0);
int l=max(len,b.len),p=0;
ans.len=l;
for(int i=1;i<=l;i++){
ans.c[i]=c[i]+b.c[i]+p;
p=ans.c[i]/10;
ans.c[i]%=10;
}
if(p) ans.c[++ans.len]=p;
return ans;
}
num operator *(const num &b)const{	// High precision times high precision
num ans(0);
int l=len+b.len-1,p=0;
for(int i=1;i<=len;i++)
for(int j=1;j<=b.len;j++)
ans.c[i+j-1]+=c[i]*b.c[j];
for(int i=1;i<=l;i++){
ans.c[i+1]+=ans.c[i]/10;
ans.c[i]%=10;
}
if(ans.c[l+1]) l++;ans.len=l;
return ans;
}
num operator *(int &x){	// High precision multiplication and low precision
int p=0;
for(int i=1;i<=len;i++){
c[i]=c[i]*x+p;
p=c[i]/10;
c[i]%=10;
}
while(p){
c[++len]=p;
p/=10;
c[len]%=10;
}
return *this;
}
};
void Print(num a){
while(!a.c[a.len]&&a.len>1) a.len--;
for(int i=a.len;i;i--)
printf("%d",a.c[i]);
printf("\n");
}
int n,k;
num f[N];
int a[N],b[N];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1),sort(b+1,b+n+1);
f=1;
for(int i=1;i<=n;i++){
int cnt=0,ii=i&1;
for(int j=0;j<=i;j++) f[ii][j]=0;
if(a[i]>=b[i]){
for(int j=1;j<=i;j++) if(a[j]>=b[i]) cnt++;
for(int j=0;j<=i;j++)
f[ii][j]=f[!ii][j]*(j+cnt);
for(int j=1;j<=i-cnt;j++)
f[ii][j]=(f[ii][j]+f[!ii][j-1]*(i-(j-1)-cnt));
}
else {
for(int j=1;j<i;j++) if(b[j]>a[i]) cnt++;
for(int j=cnt;j<=i;j++)
f[ii][j]=f[!ii][j]*(j-cnt);
for(int j=1;j<=i;j++)
f[ii][j]=(f[ii][j]+f[!ii][j-1]*(i-(j-1)+cnt));
}
}
num ans;
for(int i=0;i<=k;i++) ans=ans+f[n&1][i];
Print(ans);
return 0;
}



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.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.


https://chowdera.com/2021/08/20210810084312096W.html