情之所至,甘之如饴

题目

n对夫妇过情人节,每一位男士送每一位女士若干朵玫瑰,若一位男士送给别人妻子的花的数量总和≥送给自己妻子的花的数量,那么妻子就会不高兴。当他们互相赠送完毕后发现,对于任意一位妻子,她均可以把所有的男士分为两组,使得每组男士送给自己的花的数目之和一样多。

求证:至少有一位妻子会不高兴。

来源

白俄罗斯竞赛题。

思路

反证法。本题虽然披着组合数学难题的外衣,但本质上是一道代数题。运用数学语言和符号将所有已知条件都表示出来,就能看出端倪。

解答

将所有男士编号为${a_1},{a_2},{a_3},…,{a_n} $, 所有女士编号为${b_1},{b_2},{b_3},…,{b_n}$.用${A[i][j]} $表示第i位丈夫送给第j位妻子的花的数量。

则本题就是考察一个$n*n$的二维数组。

反证法,假设没有妻子不高兴,则对于所有的$ j \in \{1,2,…,n\} $, 均有$ A[j][j]>\sum\limits_{i = 1}^n {A[j][i]}-A[j][j]$.

移项,化简得$A[j][j] > \sum\limits_{i = 1}^n {A[j][i]}$.

对于所有的$j \in \{1,2,…,n\}$,均有.

.

矛盾!证毕!

用于求$\left( {\begin{array}{*{20}{c}}{n + m}\\m\end{array}} \right)\bmod p$, $p$为质数.

当然也要结合快速幂,不过这里是利用快速幂求逆元的啦~

代码分享


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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
//Lucas定理
//结合快速幂使用
typedef long long ll;
int n,m,p,T;
ll qpow(ll x,ll m){
if(m==0) return 1;
ll tmp=qpow(x,m>>1);
tmp=(tmp*tmp)%p;
if(m%2==1) tmp=(tmp*x)%p;
return tmp;
}
ll getc(ll n,ll m){
if(m>n) return 0;
if(m>n-m) m=n-m;
ll s1=1,s2=1;
for(int i=0;i<m;i++){
s1=s1*(n-i)%p;
s2=s2*(i+1)%p;
}
return s1*qpow(s2,p-2)%p;
}
ll lucas(ll n,ll m){
if(m==0) return 1;
return getc(n%p,m%p)*lucas(n/p,m/p)%p;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&p);
printf("%d\n",lucas(n+m,m));
}
return 0;
}
</pre>

题目


给定整数n,求卡特兰数的第n项。

分析


利用杨辉三角性质打表算出组合数即可计算。

代码分享


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
//Catalan数:求C(2n,n)/n+1
long long a[100][100],n;

int main() {
scanf("%lld",&n);
a[1][1]=a[1][2]=1;
for(long long i=2;i<=2*n;i++){
for(long long j=1;j<=i+1;j++){
a[i][j]=a[i-1][j]+a[i-1][j-1];
//printf("%d ",a[i][j]);
}
//printf("\n");
}
long long ans=a[2*n][n+1]/(n+1);
printf("%lld\n",ans);
return 0;
}

题面传送门

解题思路


组合数与杨辉三角有着千丝万缕的联系,不得不说小学奥数的知识在OI中用处还是蛮大的。(不知道杨辉三角是啥?)杨辉三角与组合数最重要的一个联系在于,第n行的m个数可表示为$ \left( {\begin{array}{*{20}{c}} {m - 1}\\ {n - 1} \end{array}} \right) $,即为从n-1个不同元素中取m-1个元素的组合数。

这就意味着对于每一次询问,我们无需现算出组合数的值,采用打表来实现即可。这样一来,时间复杂度就大大降低了。

那么预处理好杨辉三角形,还有T组询问怎么办?

我们可以用一个叫做矩阵和(又叫做二维前缀和)的东西(就是下面的S数组)。

给个口诀吧:上加左 减左上 加自己

这样预处理只需要2000*2000的时间,而面对T次询问,每次询问只需要( O(1) )的时间就可以回答,是不是超级方便!

代码分享


read是读入优化函数,然后处理询问的时候用了一个三目运算符,其余的就基本上没有难于理解的地方了。。。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
template<class T>void read(T &x) {
register int c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
int n,m,k,t;
int a[2002][2002],s[2002][2002];
int main(){
read(t);read(k);
a[1][1]=1;
for(register int i=0;i<=2000;i++) a[i][0]=1;
for(register int i=2;i<=2000;i++)
{
for(register int j=1;j<=i;j++)
{
a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;
}
}
for(register int i=1;i<=2000;i++)
{
for(register int j=1;j<=i;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(a[i][j]==0) s[i][j]++;
}
s[i][i+1]+=s[i][i];
}
while(t--)
{
read(n);read(m);
m=m>n?n:m;
printf("%d\n",s[n][m]);
}
return 0;
}

题目传送门

解题思路

最开始看题目想到暴力dfs,但是拿不到全分。本题其实在考察组合数学中的全错位排列问题,即:重新排列棋子,每一个棋子都不在原来的位置(也就是本本题所说的障碍),有多少种放置方法。
个棋子有种放置方法。显然
我们还能推得
这样一来,输入数据中的棋盘便没有任何意义了,因为对于任何满足要求的棋盘,方案总数相同。
知道了计算方法,我们只需写个高精度就可以完美AC了。

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
#include <iostream>
#include <cstdio>
using namespace std;
template<class T>void read(T &x) {
register ll c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
int n;
int d[222][100010];
void calc(int cur)
{
int x=0;
for(int i=1;i<100010;i++)
{
d[cur][i]=d[cur-1][i]+d[cur-2][i]+x;
x=d[cur][i]/10;
d[cur][i]%=10;
}
x=0;
for(int i=1;i<100010;i++)
{
d[cur][i]=d[cur][i]*(cur-1)+x;
x=d[cur][i]/10;
d[cur][i]%=10;
}
}
int main()
{
read(n);
d[2][1]=1;
if(n==1 || n==2)
{
printf("%d\n",n-1);
return 0;
}
for(int i=3;i<=n;i++) calc(i);
int len=100009;
while(d[n][len]==0) len--;
while(len) printf("%d",d[n][len--]);
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k