Article From:https://www.cnblogs.com/EdSheeran/p/9061037.html

# P2822 Combinatorial number problem

## Title Description

Combinatorial numberC_n^m

C_n^m=\frac{n!}{m!(n-m)!}

Among themn!=1\times2\times\cdots\times n

Shallots want to know if they are given.n,m

## Input-output format

Input format:

The first line has two integerst,k

Nextt

Output format:

Collectivet

## Input and output sample

Input sample #1: replication

1 2
3 3
Output sample #1: replication

1
Input sample #2: replication

2 5
4 5
6 7
Output sample #2: replication

0
7


## Explain

【Example 1 illustrates]

In all possible circumstances, onlyC_2^1 = 2

Solve the problem: the Yang Hui triangle is the combination number, the middle group of data is ignored M< N is WA, not preprocessing; the sum of two dimensional tree array can be better pretreated by DP;

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,t,N;
int k1, k2;
const int M = 2010;
ll c1[M][M],c2[M][M],a1[M][M],a2[M][M];
void add(int x, int y, int k){
x++,y++;
if(k == 1){
for( ; x <= N; x += x&(-x))
for(int j = y ; j <= N; j += j&(-j))
a1[x][j]++;
}
if(k == 2){
for( ; x <= N; x += x&(-x))
for(int j = y ; j <= N; j += j&(-j))
a2[x][j]++;
}

}
ll sum(int x, int y, int k){
ll ans = 0;
x++,y++;
if(k == k1){
for( ; x > 0; x -= x&(-x))
for(int j = y ; j > 0; j -= j&(-j))
ans += a1[x][j];
}
if(k == k2){
for( ; x > 0; x -= x&(-x))
for(int j = y ; j > 0; j -= j&(-j))
ans += a2[x][j];
}
return ans;
}
void init(int a, int b, int n){
k1 = a, k2 = b, N = n;
c1[0][0] = c2[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= i; j++){
if(!j)c1[i][j] = c2[i][j] = 1;
else c1[i][j] = (c1[i - 1][j-1] + c1[i - 1][j]) % k1,
c2[i][j] = (c2[i - 1][j-1] + c2[i - 1][j]) % k2;
}

}
int main()
{
// freopen("problem.in","r",stdin);
// freopen("problem.out","w",stdout);
scanf("%d%d",&t,&k);
switch(k){
case 2: case 3: init(2, 3, 5);break;
case 4: case 5: init(4, 5, 10);break;
case 6: case 7: init(6, 7, 12);break;
case 8: case 9: init(8, 9, 105);break;
case 10: case 11: init(10, 11, 2005);break;
case 12: case 13: init(12, 13, 75);break;
case 14: case 15: init(14, 15, 105);break;
case 16: case 17: init(16, 17, 105);break;
case 18: case 19: init(18, 19, 2005);break;
case 20: case 21: init(20, 21, 2005);break;
}
while(t--){
scanf("%d%d",&n,&m);
printf("%lld\n",sum(n, m, k));

}
return 0;
}

View Code

# P2827 Earthworm

## Title Description

In this problem, we will use symbols\lfloor c \rfloor

The recent earthworm in crickets has become a disaster! The fleas of the flea country next door also had no way to take the earthworms. The king of crickets had to ask the magic knife to help them destroy the earthworms.

The crickets are now shared by the cricketsn

Every second, the magic knife will accurately find the longest one among all the earthworms (if there are multiple ones), and cut them into two halves. The location of the earthworm by a knife is a constant.p

King cricket knows that this is not a permanent solution, because earthworms will not only grow more and more, but will also grow longer. The king of crickets decided to turn to a mysterious figure with a great shortage of power, but he needed help for the rescue.m

The cricket king wants to know thism

• m
• m

The cricket king knows how to do it, of course. But he wants to test you…

## Input-output format

Input format:

The first line contains six integersn,m,q,u,v,t

Second lines includen

The two adjacent numbers in the same line are separated by one space.

Guarantee1 \leq n \leq 10^5

Output format:

First line output\left \lfloor \frac{m}{t} \right \rfloor

Second lines output\left \lfloor \frac{n+m}{t} \right \rfloor

The two adjacent numbers in the same line are separated by one space. Even if a row needs no output, you should output a blank line.

## Input and output sample

Input sample #1: replication

3 7 1 1 3 1
3 3 2
Output sample #1: replication

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
Input sample #2: replication

3 7 1 1 3 2
3 3 2
Output sample #2: replication

4 4 5
6 5 4 3 2
Input sample #3: replication

3 7 1 1 3 9
3 3 2
Output sample #3: replication

//Empty lineTwo

## Explain

【Example interpretation 1]

Before the arrival of the sword hand, the length of the 3 earthworms was 3,3,2.

1After 3 seconds, a worm with a length of about 1 was cut into two earthworms with a length of 1 and 2. The length of the earthworms increased by 1. The length of the final 4 earthworms were (1,2) and 4,3 respectively. Brackets indicate that an earthworm has been cut off in this position.

2Seconds later: an earthworm with a length of 4 was cut into 1 and 3. The length of 5 earthworms were as follows: 2,3, (1,3), and 4.

3Second: an earthworm with a length of 4 is cut off. The length of the 6 earthworms were: 3,4,2,4, (1,3).

4Second: an earthworm with a length of 4 is cut off. The length of the 7 earthworms were 4, (1,3), and 3,5,2,4 respectively.

5Second: an earthworm with a length of 5 is cut off. The length of 8 earthworms was 5,2,4,4, (1,4), 3,5 respectively.

6Second: an earthworm with a length of 5 is cut off. The length of 9 earthworms was: (1,4), 3,5,5,2,5,4,6.

7Second: an earthworm with a length of 6 is cut off. The length of 10 earthworms was 2,5,4,6,6,3,6,5, (2,4). Therefore, the length of earthworms cut in 7 seconds is 3,4,4,4,5,5,6 in sequence. After 7 seconds, the length of all earthworms from large to small is 66,6,5,5,4,4,3,2,2

【Example interpretation 2]

Only t=2 in this data is different from the previous data. You only need to output one number per two rows.

Although the last row of the first line has 6 output, the second row will still have to start again from the second number.

【Example interpretation 3]

Only t=9 in this data is different from the previous data.

Note that the first row has no output, but it also exports a blank line.

【Data range]

Answer: open three queues, 1 stored in the original, 2 storage first, 3 storage second, each time to find the largest of the 3 queues, can ensure that the queue is monotonically decreasing, proved as follows:

if La > Lb, After M seconds, La1 = P * La + m*q, La2 = (1-P) * L a + m* Q;

At this time, B is cut, Lb1 = p* (Lb +m*q), Lb2 = (1-p) * (Lb + m*q); (P < 1)

La1 > Lb1 , La2 > Lb2;

This problem often happens when you merge 3 queues. Do not open another array.

#include <bits/stdc++.h>

using namespace std;
#define ll long long
ll w[4][8000005], a[8000005];
int h[4],tt[4];
const ll inf = 1e15;
bool cmp(ll a, ll b){return a>b;}
ll f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}

int main()
{
//freopen("earthworm.in","r",stdin);
//freopen("earthworm.out","w",stdout);
double p = 0;
int cnt = 0, n, m, q, u, v, t;
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
p = u*1.0 / v;
for(int i = 1; i <= n; i++)read(w[1][i]);
sort(w[1]+1,w[1]+1+n,cmp);
h[1] = h[2] = h[3] = 1;
tt[1] = n; tt[2] = tt[3] = 0;
int tot = n;
for(int i = 1; i <= m; i++){
ll b, c, mx = -inf;
tot++;
int mh;
for(int j = 1; j <= 3; j++)
if(w[j][h[j]] > mx && h[j] <= tt[j]) mx = w[j][h[j]], mh = j;
h[mh]++;
//printf("%I64d %d  ",mx+cnt,mh);
mx += cnt;
if(i % t == 0)printf("%lld ",mx);
b = floor(p*mx); c = mx- b;
cnt += q;
w[2][++tt[2]] = b-cnt; w[3][++tt[3]] = c-cnt;
}

printf("\n");
int qq = 0;
for(int i = 1; i <= tot; i++){
ll mx = -inf;
int mh;
for(int j = 1; j <= 3; j++)
if(w[j][h[j]] > mx && h[j] <= tt[j]) mx = w[j][h[j]], mh = j;
h[mh]++;
if(i%t == 0)printf("%lld ",mx+cnt);
}

return 0;
}

View Code

# P2831 Angry Birds

## Title Description

Kiana Recently indulged in a magical game can not extricate themselves.

In short, this game is done on a flat surface.

A slingshot is located(0,0)

When the bird falls back to the groundx

In a certain level of the game, the first quadrant of the plane hasn

If a bird’s flight path passes through\left( x_i, y_i \right)

If a bird’s flight path does not pass through\left( x_i, y_i \right)

For example, if two piglets are located respectively(1,3)

The purpose of this game is to destroy all piglets by launching small birds.

Every level of the magic game is hard for Kiana, so Kiana has also entered some mysterious instructions so that it can finish the game more easily. These instructions will be detailed in the input format.

Suppose there’s a total of this gameT

## Input-output format

Input format:

The first line contains a positive integer.T

This is the following.T

Ifm=0

Ifm=1

Ifm=2

Guarantee1\leq n \leq 18

In the preceding article\lceil c \rceil

Output format:

Output one line in order for each pass.

Each row of the output contains a positive integer, which represents the minimum number of birds required for all pigs in the corresponding checkpoints.

## Input and output sample

Input sample #1: replication

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
Output sample #1: replication

1
1
Input sample #2: replication

3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00
Output sample #2: replication

2
2
3

Input sample #3: replication

1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99
Output sample #3: replication

6


## Explain

【Example interpretation 1]

There are two levels in this set of data.

The first card is the same as the case in the problem description. 2 small pigs are located (1.00,3.00) and (3.00,3.00), and only a bird that will launch a flight path of y = -x^2 + 4x can eliminate them.

There are 5 piglets in the second checkpoints, but after observation we can find that their coordinates are on the parabola y = -x^2 + 6x, so the Kiana only needs to launch a bird to kill all the pigs.

【Data range]

Answer: the original problem is also wrong, should reflect;

Each pig has two states: hitting and not hitting, so the shape is DP;

O(N*N*2^N) + O(N*N*N) Preconditioning

dp[s | g[i][j] ] = min(dp[s] +1), dp[0] = 0;

dp[s] How many birds are required for s state? G[i][j] is a parabola of pretreated birds that can hit those pigs; if the g[i][j] is useless, it will kick off or T.

#include <bits/stdc++.h>

using namespace std;
const int M = 20;
double x[M], y[M], a[M][M], b[M][M];
int g[M][M], dp[1<<20];
const double eps = 1e-6;
bool build(int i, int j){
a[i][j] = (y[i]/x[i] - y[j]/x[j]) / (x[i] - x[j]);
if(a[i][j] >= 0)return false;

b[i][j] = (y[i] - a[i][j]*x[i]*x[i]) / x[i];
return 1;
}
bool check(int i, int j, int k){
double tmp = a[i][j]*x[k]*x[k] + b[i][j] * x[k];
if(fabs(tmp - y[k]) < eps) return 1;
return 0;
}
int main()
{
//freopen("angrybirds.in","r",stdin);
//freopen("angrybirds.out","w",stdout);
int T, n, m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)scanf("%lf%lf",&x[i],&y[i]);
memset(g, 0, sizeof(g));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = 0; i <= n; i++){

for(int j = i+1; j <= n; j++){
if(!i)g[i][j] = 1<<(j-1);
else if(build(i, j)){
g[i][j] |= 1<<(i-1);
g[i][j] |= 1<<(j-1);
for(int k = 1; k <= n; k++)
if(check(i, j, k))g[i][j] |= (1<<(k-1));
}

}
}
memset(dp, 127, sizeof(dp));
dp[0] = 0;
for(int s = 0; s < (1<<n); s++)
for(int i = 0; i <= n; i++)
for(int j = i; j <= n; j++)
dp[s|g[i][j]] = min(dp[s|g[i][j]], dp[s]+1);
printf("%d\n",dp[(1<<n)-1]);
}

return 0;
}

View Code

O（N*2^N)，

#include <bits/stdc++.h>

using namespace std;
const int M = 20;
double x[M], y[M], a[M][M], b[M][M];
int g[M][M], dp[1<<20];
const double eps = 1e-6;
inline bool build(int i, int j){
a[i][j] = (y[i]/x[i] - y[j]/x[j]) / (x[i] - x[j]);
if(a[i][j] >= 0)return false;
b[i][j] = (y[i] - a[i][j]*x[i]*x[i]) / x[i];
return 1;
}
inline bool check(int i, int j, int k){
double tmp = a[i][j]*x[k]*x[k] + b[i][j] * x[k];
if(fabs(tmp - y[k]) < eps) return 1;
return 0;
}
inline int min(int a, int b){
return a < b ? a : b;
}
int down(int s){
int i = 0;
while(!(s&(1<<i)))i++;
return i+1;
}
int main()
{
// freopen("angrybirds.in","r",stdin);
// freopen("angrybirds.out","w",stdout);
int T, n, m, cnt = 0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)scanf("%lf%lf",&x[i],&y[i]);
memset(g, 0, sizeof(g));
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
if(build(i, j)){
for(int k = 1; k <= n; k++)
if(check(i, j, k))g[i][j] |= (1<<(k-1));
}

}
}
for(int i = 1; i <= (1<<n); i++)dp[i] = 28;
dp[0] = 0;
for(int s = 1; s < (1<<n); s++){
int i = down(s);
dp[s] = min(dp[s], dp[s-(1<<(i-1))]+1);
for(int j = i+1; j<= n; j++){
int ss = (s&g[i][j]);
dp[s] = min(dp[s], dp[s^ss]+1);
}
}
printf("%d\n",dp[(1<<n)-1]);
}

return 0;
}

View Code