# 40 条题解

• @ 2017-11-08 15:23:50

排列组合的题
方案数为C(n,k) * A(n,k) * A(k,k)除以每种颜色的阶乘

``````#include<iostream>
using namespace std;
long long jie[21];
int main()
{
int i,j,n,k,h,a;
long long ans;
cin>>n>>k>>h;
jie[0]=1;
jie[1]=1;
for(i=2;i<=n;i++)
jie[i]=jie[i-1]*i;
ans=(jie[n]/jie[k])/jie[n-k];
ans*=jie[n]/jie[n-k];
ans*=jie[k];
for(i=1;i<=h;i++)
{
cin>>a;
ans/=jie[a];
}
cout<<ans;
return 0;
}
``````
• @ 2016-03-23 07:35:15

记录信息
评测状态 Accepted
题目 P1166 木牛流马
递交时间 2016-03-23 07:34:59
代码语言 C++
消耗时间 0 ms
消耗内存 512 KiB
评测时间 2016-03-23 07:35:00

评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:26:26: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld",ans);
^
foo.cpp:26:26: warning: too many arguments for format [-Wformat-extra-args]

测试数据 #0: Accepted, time = 0 ms, mem = 508 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 512 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 504 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 508 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 508 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 508 KiB, score = 10

Accepted, time = 0 ms, mem = 512 KiB, score = 100

• @ 2015-10-24 15:54:57

假设每个都不同
则第一个的横坐标有n种，第二个的横坐标有n-1种，这里的排列有p(n,k)种
而纵坐标同理 因此根据乘法原理 总共的方案数应该有 p(n,k)^2个
考虑到其中的颜色相同
则答案数应该除以 num[1]! *num[2]!...*num[h]!

#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,h,num[100],vis[30][30];
typedef long long LL;
LL ans=1;
LL c(int x,int y){//x qv y
LL ret=1;
for(int i=x;i>=x-y+1;i--) ret*=i;
for(int i=y;i>=1;i--) ret/=i;
return ret;
}
LL p(int x,int y){//x qv y
LL ret=1;
for(int i=x;i>=x-y+1;i--) ret*=i;
return ret;
}
int main(){
//freopen("1166.in","r",stdin);freopen("1166.out","w",stdout);
scanf("%d%d%d",&n,&k,&h);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
if(k>n) printf("0");
else {
ans=p(n,k)*p(n,k);
for(int i=1;i<=n;i++) ans/=p(num[i],num[i]);
printf("%lld",ans);
}
return 0;
}

• @ 2015-08-26 23:39:52

#include <iostream>

using namespace std;

int fac(int n);

int main()
{
int n, k, h;
long long ans;
int a[21];
cin >> n >> k >> h;//n<=20
for (int i = 0;i < h;i++)
cin >> a[i];
if (k <= n)
{
ans = 1;
for (int i = 0, j = n;i < k;i++, j--)
{
ans *= j;
}
ans = ans*ans;
for (int i = 0;i < h;i++)
ans /= fac(a[i]);
cout << ans << endl;
}
else
cout << "0" << endl;
return 0;
}

int fac(int n)
{
int f;
if (n == 1)
f = 1;
else
f = n*fac(n - 1);
return f;
}

• @ 2015-03-10 09:26:28

#include<stdio.h>
#include<string.h>
int fac(int x)
{
int a=1;
int i;
for(i=1;i<=x;i++)
a=a*i;
return a;
}
int order(int a,int b)
{
int x=1;
int y=1;
int j;
for(j=(b-a+1);j<=b;j++)
{
x=x*j;
y=y*(j+a-b);
}
return x/y;
}
int main()
{
int n,k,h;
scanf("%d%d%d",&n,&k,&h);
int x[h];
memset(x,0,sizeof(x));
int i;
for(i=0;i<h;i++)
{
scanf("%d",&x[i]);
}
if(k<=n)
{
long long int count=1;
int y;
for(y=n-k+1;y<=n;y++)
{
count=count*y;
}
count=count*count;
int j;
for(j=0;j<h;j++)
{
count=count/fac(x[j]);
}
printf("%lld",count);
return 0;
}
else
{
printf("0");
return 0;
}
}
要注意无解的情况

• @ 2014-05-04 18:56:13

program P1166;
var
ans:Int64;
n,k,h,i,j,s:longint;
begin
ans:=1;
for i:=n-k+1 to n do
ans:=ans*i;
for i:=1 to h do
begin
for j:=2 to s do
ans:=ans div j;
end;
for i:=n-k+1 to n do
ans:=ans*i;
writeln(ans);
end.
呜呜呜呜
新手只能复制题解了

• @ 2012-08-20 16:20:54

我的题解。。。

• @ 2012-07-23 14:44:56

我一直把题目理解错啦,

以为"接下来h行为每种颜色多少个"是指每种颜色只能涂色有限制个数的牛,(错的!!)

实际上是指这个颜色的牛有这么多个,加起来和为n

用排列组合就可以完成

先假设每种牛都不同颜色的,情况总数为P(n,k)*C(n,k)*P(k,k)=P(n,k)*P(n,k)

实际上牛可能是同种颜色,所以答案为ans=P(n,k)^2/(C1!C2!...Cn!)

Ci表示每种颜色的个数。

数据类型弄成qword就可以的啦..别想复杂

• @ 2009-11-07 17:09:43

横竖n选k,所以C(n,k)^2

然后有序排列，k!(对于每一次插入马，可以看作第i次插入有i个位置）

然后染色，C(a1,k)*c(a2,k-a1)*...*c(an,k-a1-a2-...-a(n-1))，化简得:

k!/(a1!*a2!*...*an!)

所以最终结果=c(n,k)^2*k!*k!/(a1!*a2!*...*an!)

=(n!/(n-k)!)^2/(a1!*a2!*...*an!)

片段：

(n!/(n-k)!)^2:for i:=n downto n-k+1 do s:=s*i;做2遍

然后读一个数就除以它的阶乘

作一个优化，做1遍先除再做第2遍，这样有效防止溢出201

这样程序和楼下一样

• @ 2009-10-15 15:27:18

我们把题目拆成两部分进行考虑：1摆放木牛流马2给木牛流马染色。

1:递推公式（OR DP）：f=f+f*(n-j+1)

2：染色 求K的阶乘

• @ 2009-08-26 17:49:19
• @ 2009-08-26 01:33:52

用c的牛儿们谨记血的教训：输出long long(__int64)千万不可用%lld（用%I64d），否则第四点WA。

感叹~~标准对于视标准如无物的编译器是没用的~~

白白交了5次，my heart bleeding...

• @ 2009-08-22 09:02:33

TMD真猥琐~~~我才新初二呢~~！

• @ 2016-08-06 08:38:13

现在不是了

• @ 2009-08-11 19:07:40

范围的问题只要用Int64就可以了

附“参考”程序：

program P1166;

var

ans:Int64;

n,k,h,i,j,s:longint;

begin

ans:=1;

for i:=n-k+1 to n do

ans:=ans*i;

for i:=1 to h do

begin

for j:=2 to s do

ans:=ans div j;

end;

for i:=n-k+1 to n do

ans:=ans*i;

writeln(ans);

end.

• @ 2009-08-07 11:57:28

var n,k,h,i,j:longint;f:array[0..20,0..20] of qword;

a:array[1..20] of longint;

x,x1,x2:qword;

function p(x:longint):qword; {P(n)=n!}

var i:longint;

begin

p:=1;

for i:=2 to x do p:=p*i;

end;

Begin

for i:=1 to h do read(a[i]);

for i:=0 to n do

f:=1; {注意边界条件！偶就差点栽在这里}

for i:=1 to n do

for j:=1 to n do

f:=f*(n-j+1)+f; {递推式}

x:=p(k); {这之后都是关于染色的处理}

for i:=1 to h do x:=x div p(a[i]);

writeln(f[n,k]*x);

End.

• @ 2009-07-02 08:24:52

yuwanmxd的代码似乎有一个地方不对~~

for i:=1 to n do

for j:=1 to n do

f:=f*(n-j+1)+f;

其中j应该是循环木牛流马数吧~~

for i:=1 to n do

for j:=1 to k do

f:=f+f*(k-j+1);

• @ 2009-04-26 10:46:27

晕...原来不要用高精度...

• @ 2009-02-13 01:29:43

数学题。

• @ 2009-02-04 20:14:59

ans=P(n,k)^2/(C1!C2!...Cn!)

Ci表示每种颜色的个数。

当n

• @ 2008-12-05 22:10:52

回答bluesky，不是无解，我的程序全过了，具体什么情况我也不好说，看看我的程序

var n,k,h,i,j:longint;f:array[0..20,0..20] of qword;

a:array[1..20] of longint;

x,x1,x2:qword;

function p(x:longint):qword; {P(n)=n!}

var i:longint;

begin

p:=1;

for i:=2 to x do p:=p*i;

end;

Begin

for i:=1 to h do read(a[i]);

for i:=0 to n do

f:=1; {注意边界条件！偶就差点栽在这里}

for i:=1 to n do

for j:=1 to n do

f:=f*(n-j+1)+f; {递推式}

x:=p(k); {这之后都是关于染色的处理}

for i:=1 to h do x:=x div p(a[i]);

writeln(f[n,k]*x);

End.

{偶新初一，如有在数学不足之处请各位大牛指出，感激涕零(数学啊数学，让我又爱又恨。。)}

ID
1166

3

786

375

48%

7