题解

16 条题解

  • 1
    @ 2016-11-10 15:54:48

    python水过QAQ:
    python
    f=[0]*3100;
    n=int(raw_input());
    f[1]=0;
    for i in range(2,1010):
    f[i]=i*f[i-1]+(-1)**i;
    print f[n]

  • 1
    @ 2014-08-18 18:58:47

    对于每一个i,第i排有一个细菌,该细菌不能放在第i个位置
    所以有 P1,P2,P3...Pn ∈{1,2,3...n}(Pi<>i),数值方案总数即为答案
    即求全错位排列,设f[n]为方案总数,得:

    f[n]=n*f[n-1]+(-1)^n (n>1)
    f[1]=0

    由于n<=1000,用高精,数组开到3000足够

    Code(pascal):

    var
    p,f:array[1..3000]of integer;
    n,lp,lf,j:integer;

    procedure times;
    var
    i,x:integer;
    begin
    x:=0;
    for i:=1to lp do
    begin
    f[i]:=f[i]+p[i]*j+x;
    x:=f[i]div 10;
    f[i]:=f[i] mod 10;
    end;
    while x>0do
    begin
    inc(i);
    f[i]:=x mod 10;
    x:=x div 10;
    end;
    lf:=i;
    end;

    procedure deec;
    var
    k:integer;
    begin
    dec(f[1]);
    k:=1;
    while f[k]<0do
    begin
    dec(f[k+1]);
    inc(f[k],10);
    inc(k);
    end;
    if f[lf]=0then dec(lf);
    end;

    procedure innc;
    var
    k:integer;
    begin
    inc(f[1]);
    k:=1;
    while f[k]=10do
    begin
    f[k]:=1;
    inc(f[k+1]);
    inc(k);
    end;
    if f[lf+1]>0then inc(lf);
    end;

    begin
    readln(n);
    if n=1 then begin writeln(0); halt; end
    else if n=2 then begin writeln(1); halt; end;
    p[1]:=1; lp:=1;
    for j:=3 to n do
    begin
    times;
    if j mod 2=1then deec
    else innc;
    p:=f; lp:=lf;
    fillchar(f,sizeof(f),0);
    end;
    for j:=lp downto 1 do write(p[j]);
    end.

  • 0
    @ 2010-07-13 17:56:35

    var

    f:array[1..1000,1..3000]of longint;

    N,i,j,l:longint;

    s:string;

    begin

    readln(n);

    f[1,1]:=0; f[2,1]:=1; l:=1;

    for i:=3 to N do begin

    for j:=1 to l do f:=(f+f)*(i-1);

    for j:=1 to l do begin

    f:=f div 100000 +f;

    f:=f mod 100000;

    end;

    while f>0 do begin

    inc(l);

    f:=f div 100000 +f;

    f:=f mod 100000;

    end;

    end;

    write(f[N,l]);

    for i:=l-1 downto 1 do begin

    str(f[N,i],s);

    while length(s)

  • 0
    @ 2009-11-18 20:42:44

    规律....

    好像都有几条递推公式的,不过,不知道三阶递推的公式怎么求。

  • 0
    @ 2009-11-16 16:53:11

    比赛时如果想不到递推的话可以先搜索小数据,寻找规律

    当然…………as for this problem……还是直接代公式来得快……

  • 0
    @ 2009-11-16 13:57:28

    for i:=3 to n do

    begin

    cheng(x,i);

    if i mod 2=0 then

    jia(x,1)

    else

    jia(x,-1);

    end;

    我的公式比较非主流...

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-11-15 20:28:47

    错排

    f[i]:=(f+f)*(i-1)

    加个高精度解决……

  • 0
    @ 2009-11-15 11:57:45

    前10~~~

  • 0
    @ 2009-11-15 11:57:07

    这是我在比赛中第一次AC的题!!

  • 0
    @ 2009-11-13 16:22:45

    t(n)=(n-1)*(T(n-1)+T(n-2))

  • 0
    @ 2009-11-07 15:49:14

    地板

  • 0
    @ 2009-11-07 01:19:51

    。板凳。O.O

  • 0
    @ 2009-11-03 12:32:46

    细菌总数?难道是比赛题目……

  • -1
    @ 2016-05-21 11:46:55

    var
    a:array [0..10000] of longint;
    n,i,j,l:longint;
    begin
    read(n);
    if (n=1) then begin writeln(0); exit; end;
    a[1]:=1; l:=1;
    for i:=3 to n do
    begin
    for j:=1 to l do a[j]:=a[j]*i;
    for j:=1 to l+4 do
    begin
    inc(a[j+1],a[j] div 10);
    a[j]:=a[j] mod 10;
    end;
    l:=l+4;
    while (a[l]=0) do dec(l);
    if (i mod 2=0) then begin
    inc(a[1]);
    for j:=1 to l do
    begin
    inc(a[j+1],a[j] div 10);
    a[j]:=a[j] mod 10;
    end;
    if (a[l+1]<>0) then inc(l);
    end
    else begin
    dec(a[1]);
    for j:=1 to l do
    if (a[j]<0) then
    begin inc(a[j],10); dec(a[j+1]); end;
    if (a[l]=0) then dec(l);
    end;
    end;
    for i:=l downto 1 do write(a[i]);
    end.

  • 1

信息

ID
1687
难度
4
分类
组合数学 | 高精度 点击显示
标签
递交数
866
已通过
351
通过率
41%
被复制
1
上传者