40 条题解
-
2
猫粮寸断 LV 10 @ 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; } -
0
记录信息
评测状态 Accepted
题目 P1166 木牛流马
递交时间 2016-03-23 07:34:59
代码语言 C++
评测机 ShadowShore
消耗时间 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
-
0
假设每个都不同
则第一个的横坐标有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;
} -
0
#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;
} -
0
#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;
}
}
要注意无解的情况 -
0
ffffffff12138 LV 7 @ 2014-05-04 18:56:13
program P1166;
var
ans:Int64;
n,k,h,i,j,s:longint;
begin
readln(n,k,h);
ans:=1;
for i:=n-k+1 to n do
ans:=ans*i;
for i:=1 to h do
begin
readln(s);
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.
呜呜呜呜
新手只能复制题解了 -
0
横竖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
这样程序和楼下一样 -
0
还好顺利过了这题。。。。
程序：http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!173.entry
-
0
qyjubriskxp LV 10 @ 2009-08-26 01:33:52
用c的牛儿们谨记血的教训：输出long long(__int64)千万不可用%lld（用%I64d），否则第四点WA。
感叹~~标准对于视标准如无物的编译器是没用的~~
白白交了5次，my heart bleeding... -
0
-
0
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
readln(n,k,h);
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. -
0
回答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
readln(n,k,h);
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.
{偶新初一，如有在数学不足之处请各位大牛指出，感激涕零(数学啊数学，让我又爱又恨。。)}
猫粮寸断
LV 10
@ 2017-11-08 15:23:50
