有关ACM一道题，请各位大牛帮帮忙！！！

题目包含多组输入数据。

比如，程序的输入可能是这样

3

5 7 5

5

5 5 3 6 6

0

而按你的程序只能输出第一组的结果。最后面那个0代表输入结束。

#include <stdioh>

int main(){

int n,i;

__int64 f[100];

f[0]=f[1]=1;

for (i=2;i<=90;i++)

f[i]=f[i-1]+f[i-2];

while (scanf("%d",&n)&&n) printf("%I64d\n",f[n]);

return 0;

}

加油哈~

我想说下我的了解。很多ACMer入门的时分，都被告知：做个500多道就变牛了。其实，这既不是充沛条件、也不会是必要条件。我们的主要目标大致四点：

进步编程才能；

学习算法，（读书，读论文，包括做一些标题考证）；

准备好面临将到来的应战（熟习题型，调整心态）；

启示思想。

这里四个目的，从锻炼的角度上，重要性逐次递加，由于前面的要素是后面的根底。而是后面的目的，想达成越为不易。

关于第二点，acm大部分都是依靠算法支撑，也是显而易见的不加多说。实际运用上也是非常广泛的。

算法书有很多可以参考：

ConcreteMathematics --- A Foundation For Computer Science

Ronald L Graham ， Donald E Knuth ， Oren Patashnik

Introductionto Algorithms

Thomas H Cormen ，CharlesE Leiserson ，Ronald L Rivest ，CliffordStein

（强烈推荐）实用算法的分析和程序设计-吴文虎王建德

（大名鼎鼎的“黑书”。内容包括了竞赛需要的各种算法，各种层次的读者都适合。）

网络算法与复杂性理论 -谢政李建平

（强烈推荐）算法+数据结构=程序-NWirth

（Pascal语言的发明人Wirth教授的名著，深入阐述了算法与数据结构的关系，对每个算法都提供详细的Pascal源程序，适合各种水平的读者。）

你自己测试不够，比如下面这组你的答案是错的：

4

1 1

4 1

8 5

9 2

正确答案应该是325，你的是2。

这说明你的代码逻辑有问题。另外说些其他问题：

1、ACM的题目大多都是多组数据，输入输出描述中有“每组测试数据……”之类的，这多组数据是要在一次运行下输入的，而不是运行多次。你最好先学习下关于做ACM题目的各种常见输入输出方式，这是最基本的。

2、“第一行为一个正整数N”，输入明明是一个整数，你读入却用的是float，实数都是有可能存在误差的，比如输入5，T1的值可能是500000001，这不是一定会出现，但是一旦出现，你的循环for (j = 0; j < T1 - 1; j++)就会比你预想的多循环一次。

这种题目然做过的，

意思比较简单，就由 m 个共 0 和 n 个 1 组成一个串，但从左到右要1出现的次数不少于0出现的次数。

由大牛的算法： 结果就是 C(m+n, n) - C(m+n, m-1) 再取模，我们可以对式子化简一下就是：

(n+m)！

(n-m+1) / ((m)！ (n+1)！)

再取模，但由于组合数很大，直接用大数乘除就会超时了，看了别人的报告才知道原来可以用素数化简快速求模的， n! = 2^p[i]

3^p[i] 5^p[i] 再求模就可以很快了~(^ = ^)~。。。

#include<iostream>

#include<stdioh>

#include<stringh>

using namespace std;

#define M 2000005

#define mm 20100501

bool sig[M];

int prime[150000], p[150000], len; // prime 记录素数， p 记录素数的幂 len 记录长度

void getprime() // 筛法找素数

{

int i,j,k=0;

prime[k++] = 2;

for(i=3; i<=M; i+=2)

{

if( !sig[i] )

{

prime[k++] = i;

for(j=i; j<=M; j+=i)

sig[j] = 1;

}

}

}

void get(int k, int s) // K! 的素数分解, S为指数的加减(分母，分子)

{

int i, mid;

for(i=0; prime[i]<=k && prime[i]; i++)

{

mid = k;

while(mid)

{

if(s)

p[i] += mid/prime[i];

else

p[i] -= mid/prime[i];

mid /= prime[i];

}

}

if(len < i)

len = i;

}

__int64 cal() // 计算结果 (prime[i]^p[i]) % mm

{

__int64 i,ans = 1;

for(i=0; i<=len; i++)

{

if( p[i] )

{

__int64 t = prime[i], b = p[i], ret = 1;

while(b) //计算 (t^b) % mm

{

if(b%2) ret = t %mm;

t = tt%mm;

b /= 2;

}

ans = ( ansret ) % mm;

}

}

return ans;

}

int main()

{

int t,m,n,i,mid;

__int64 ans;

getprime();

cin>>t;

while(t--)

{

cin>>n>>m;

len = 0;

memset(p, 0, sizeof(p));

mid = n-m+1; //先前要把 n-m+1 的因子加进 P 中去才能使 (m+n)! / ((m)!(n+1)!) 整除

for(i=0; mid>1; i++)

{

if( mid%prime[i] == 0)

{

while(mid%prime[i]==0)

{

p[i] += 1;

mid /= prime[i];

}

}

}

get(m+n, 1);

get(m, 0);

get(n+1, 0);

ans = cal();

printf("%I64d\n", ans);

}

return 0;

}

可以用素数分解法，

先求出上面和下面的素数表示，然后约分后，再用求幂公式

本程序由国外的Vulture大哥编写，并公布了源码，这个是他95年的一个作品。真的很佩服他！太强了。好好学习啊！！！！

;编译方法： 1 tasm 3dasm

; 2 tlink 3dobj

; 3 exe2bin 3dexe 3dcom

; Assembler Program By Vulture ;

; 3D-system example Use the following formulas to rotate a point: ;

; ;

; Rotate around x-axis ;

; YT = Y COS(xang) - Z SIN(xang) / 256 ;

; ZT = Y SIN(xang) Z COS(xang) / 256 ;

; Y = YT ;

; Z = ZT ;

; ;

; Rotate around y-axis ;

; XT = X COS(yang) - Z SIN(yang) / 256 ;

; ZT = X SIN(yang) Z COS(yang) / 256 ;

; X = XT ;

; Z = ZT ;

; ;

; Rotate around z-axis ;

; XT = X COS(zang) - Y SIN(zang) / 256 ;

; YT = X SIN(zang) Y COS(zang) / 256 ;

; X = XT ;

; Y = YT ;

; ;

; Divide by 256 coz we have multiplyd our sin values with 256 too ;

; This example isn’t too fast right now but it’ll work just fine ;

; ;

; Current Date: 6-9-95 Vulture ;

; ;

IDEAL ; Ideal mode

P386 ; Allow 80386 instructions

JUMPS ; Tasm handles out of range jumps (rulez!:))

SEGMENT CODE ; Code segment starts

ASSUME cs:code,ds:code ; Let cs and ds point to code segment

ORG 100h ; Make a COM file

START: ; Main program

mov ax,0013h ; Init vga

int 10h

mov ax,cs

mov ds,ax ; ds points to codesegment

mov ax,0a000h

mov es,ax ; es points to vga [Page]

lea si,[Palette] ; Set palette

mov dx,3c8h

xor al,al

out dx,al

mov dx,3c9h

mov cx,1893

repz outsb

; === Set some variables ===

mov [DeltaX],1 ; Initial speed of rotation

mov [DeltaY],1 ; Change this and watch what

mov [DeltaZ],1 ; happens It’s fun!

mov [Xoff],256

mov [Yoff],256 ; Used for calculating vga-pos

mov [Zoff],300 ; Distance from viewer

MainLoop:

call MainProgram ; Yep do it all ;-)

in al,60h ; Scan keyboard

cmp al,1 ; Test on ESCAPE

jne MainLoop ; Continue if not keypressed

; === Quit to DOS ===

mov ax,0003h ; Back to textmode

int 10h

lea dx,[Credits]

mov ah,9

int 21h

mov ax,4c00h ; Return control to DOS

int 21h ; Call DOS interrupt

; === Sub-routines ===

PROC WaitVrt ; Waits for vertical retrace to reduce \"snow\"

mov dx,3dah

Vrt:

in al,dx

test al,8

jnz Vrt ; Wait until Verticle Retrace starts

NoVrt:

in al,dx

test al,8

jz NoVrt ; Wait until Verticle Retrace ends

ret ; Return to main program

ENDP WaitVrt

PROC UpdateAngles

; Calculates new x,y,z angles

; to rotate around

mov ax,[XAngle] ; Load current angles

mov bx,[YAngle]

mov cx,[ZAngle]

add ax,[DeltaX] ; Add velocity

and ax,11111111b ; Range from 0255

mov [XAngle],ax ; Update X

add bx,[DeltaY] ; Add velocity

and bx,11111111b ; Range from 0255

mov [YAngle],bx ; Update Y

add cx,[DeltaZ] ; Add velocity

and cx,11111111b ; Range from 0255

mov [ZAngle],cx ; Update Z

ret

ENDP UpdateAngles

PROC GetSinCos

; Needed : bx=angle (0255)

; Returns: ax=Sin bx=Cos

push bx ; Save angle (use as pointer)

shl bx,1 ; Grab a word so bx=bx2 [Page]

mov ax,[SinCos bx] ; Get sine

pop bx ; Restore pointer into bx

push ax ; Save sine on stack

add bx,64 ; Add 64 to get cosine

and bx,11111111b ; Range from 0255

shl bx,1 ; 2 coz it’s a word

mov ax,[SinCos bx] ; Get cosine

mov bx,ax ; Save it bx=Cos

pop ax ; Restore ax=Sin

ret

ENDP GetSinCos

PROC SetRotation

; Set sine & cosine of x,y,z

mov bx,[XAngle] ; Grab angle

call GetSinCos ; Get the sine&cosine

mov [Xsin],ax ; Save sin

mov [Xcos],bx ; Save cos

mov bx,[Yangle]

call GetSinCos

mov [Ysin],ax

mov [Ycos],bx

mov bx,[Zangle]

call GetSinCos

mov [Zsin],ax

mov [Zcos],bx

ret

ENDP SetRotation

PROC RotatePoint ; Rotates the point around x,y,z

; Gets original x,y,z values

; This can be done elsewhere

movsx ax,[Cube si] ; si = X (movsx coz of byte)

mov [X],ax

movsx ax,[Cube si 1] ; si 1 = Y

mov [Y],ax

movsx ax,[Cube si 2] ; si 2 = Z

mov [Z],ax

; Rotate around x-axis

; YT = Y COS(xang) - Z SIN(xang) / 256

; ZT = Y SIN(xang) Z COS(xang) / 256

; Y = YT

; Z = ZT

mov ax,[Y]

mov bx,[XCos]

imul bx ; ax = Y Cos(xang)

mov bp,ax

mov ax,[Z]

mov bx,[XSin]

imul bx ; ax = Z Sin(xang)

sub bp,ax ; bp = Y Cos(xang) - Z Sin(xang)

sar bp,8 ; bp = Y Cos(xang) - Z Sin(xang) / 256

mov [Yt],bp

mov ax,[Y]

mov bx,[XSin]

imul bx ; ax = Y Sin(xang)

mov bp,ax

mov ax,[Z]

mov bx,[XCos]

imul bx ; ax = Z Cos(xang)

add bp,ax ; bp = Y SIN(xang) Z COS(xang) [Page]

sar bp,8 ; bp = Y SIN(xang) Z COS(xang) / 256

mov [Zt],bp

mov ax,[Yt] ; Switch values

mov [Y],ax

mov ax,[Zt]

mov [Z],ax

; Rotate around y-axis

; XT = X COS(yang) - Z SIN(yang) / 256

; ZT = X SIN(yang) Z COS(yang) / 256

; X = XT

; Z = ZT

mov ax,[X]

mov bx,[YCos]

imul bx ; ax = X Cos(yang)

mov bp,ax

mov ax,[Z]

mov bx,[YSin]

imul bx ; ax = Z Sin(yang)

sub bp,ax ; bp = X Cos(yang) - Z Sin(yang)

sar bp,8 ; bp = X Cos(yang) - Z Sin(yang) / 256

mov [Xt],bp

mov ax,[X]

mov bx,[YSin]

imul bx ; ax = X Sin(yang)

mov bp,ax

mov ax,[Z]

mov bx,[YCos]

imul bx ; ax = Z Cos(yang)

add bp,ax ; bp = X SIN(yang) Z COS(yang)

sar bp,8 ; bp = X SIN(yang) Z COS(yang) / 256

mov [Zt],bp

mov ax,[Xt] ; Switch values

mov [X],ax

mov ax,[Zt]

mov [Z],ax

; Rotate around z-axis

; XT = X COS(zang) - Y SIN(zang) / 256

; YT = X SIN(zang) Y COS(zang) / 256

; X = XT

; Y = YT

mov ax,[X]

mov bx,[ZCos]

imul bx ; ax = X Cos(zang)

mov bp,ax

mov ax,[Y]

mov bx,[ZSin]

imul bx ; ax = Y Sin(zang)

sub bp,ax ; bp = X Cos(zang) - Y Sin(zang)

sar bp,8 ; bp = X Cos(zang) - Y Sin(zang) / 256

mov [Xt],bp

mov ax,[X]

mov bx,[ZSin]

imul bx ; ax = X Sin(zang)

mov bp,ax

mov ax,[Y]

mov bx,[ZCos]

imul bx ; ax = Y Cos(zang)

add bp,ax ; bp = X SIN(zang) Y COS(zang) [Page]

sar bp,8 ; bp = X SIN(zang) Y COS(zang) / 256

mov [Yt],bp

mov ax,[Xt] ; Switch values

mov [X],ax

mov ax,[Yt]

mov [Y],ax

ret

ENDP RotatePoint

PROC ShowPoint

; Calculates screenposition and

; plots the point on the screen

mov ax,[Xoff] ; XoffX / Z Zoff = screen x

mov bx,[X]

imul bx

mov bx,[Z]

add bx,[Zoff] ; Distance

idiv bx

add ax,[Mx] ; Center on screen

mov bp,ax

mov ax,[Yoff] ; YoffY / Z Zoff = screen y

mov bx,[Y]

imul bx

mov bx,[Z]

add bx,[Zoff] ; Distance

idiv bx

add ax,[My] ; Center on screen

mov bx,320

imul bx

add ax,bp ; ax = (y320) x

mov di,ax

mov ax,[Z] ; Get color from Z

add ax,100d ; (This piece of code could be improved)

mov [byte ptr es:di],al ; Place a dot with color al

mov [Erase si],di ; Save position for erase

ret

ENDP ShowPoint

PROC MainProgram

call UpdateAngles ; Calculate new angles

call SetRotation ; Find sine & cosine of those angles

xor si,si ; First 3d-point

mov cx,MaxPoints

ShowLoop:

call RotatePoint ; Rotates the point using above formulas

call ShowPoint ; Shows the point

add si,3 ; Next 3d-point

loop ShowLoop

call WaitVrt ; Wait for retrace

xor si,si ; Starting with point 0

xor al,al ; Color = 0 = black

mov cx,MaxPoints

Deletion:

mov di,[Erase si] ; di = vgapos old point

mov [byte ptr es:di],al ; Delete it

add si,3 ; Next point

loop Deletion

ret

ENDP MainProgram

; === DATA ===

Credits DB 13,10,\"Code by Vulture / Outlaw Triad\",13,10,\"$\"

Label SinCos Word ; 256 values

dw 0,6,13,19,25,31,38,44,50,56 [Page]

dw 62,68,74,80,86,92,98,104,109,115

dw 121,126,132,137,142,147,152,157,162,167

dw 172,177,181,185,190,194,198,202,206,209

dw 213,216,220,223,226,229,231,234,237,239

dw 241,243,245,247,248,250,251,252,253,254

dw 255,255,256,256,256,256,256,255,255,254

dw 253,252,251,250,248,247,245,243,241,239

dw 237,234,231,229,226,223,220,216,213,209

dw 206,202,198,194,190,185,181,177,172,167

dw 162,157,152,147,142,137,132,126,121,115

dw 109,104,98,92,86,80,74,68,62,56

dw 50,44,38,31,25,19,13,6,0,-6

dw -13,-19,-25,-31,-38,-44,-50,-

56,-62,-68

dw -74,-80,-86,-92,-98,-104,-109,-115,-121,-126

dw -132,-137,-142,-147,-152,-157,-162,-167,-172,-177

dw -181,-185,-190,-194,-198,-202,-206,-209,-213,-216

dw -220,-223,-226,-229,-231,-234,-237,-239,-241,-243

dw -245,-247,-248,-250,-251,-252,-253,-254,-255,-255

dw -256,-256,-256,-256,-256,-255,-255,-254,-253,-252

dw -251,-250,-248,-247,-245,-243,-241,-239,-237,-234

dw -231,-229,-226,-223,-220,-216,-213,-209,-206,-202

dw -198,-194,-190,-185,-181,-177,-172,-167,-162,-157

dw -152,-147,-142,-137,-132,-126,-121,-115,-109,-104

dw -98,-92,-86,-80,-74,-68,-62,-56,-50,-44

dw -38,-31,-25,-19,-13,-6

Label Cube Byte ; The 3d points

c = -35 ; 5x5y5z (=125) points

rept 5

b = -35

rept 5

a = -35

rept 5

db a,b,c

a = a 20

endm

b = b 20

endm

c = c 20

endm

Label Palette Byte ; The palette to use

db 0,0,0 ; 633 gray-tint

d = 63

rept 63

db d,d,d

db d,d,d

db d,d,d

d = d - 1

endm

X DW ; X variable for formula

Y DW

Z DW

Xt DW ; Temporary variable for x

Yt DW

Zt DW

XAngle DW 0 ; Angle to rotate around x

YAngle DW 0

ZAngle DW 0

DeltaX DW ; Amound Xangle is increased each time

DeltaY DW

DeltaZ DW

Xoff DW

Yoff DW

Zoff DW ; Distance from viewer

XSin DW ; Sine and cosine of angle to rotate around

XCos DW

YSin DW [Page]

YCos DW

ZSin DW

ZCos DW

Mx DW 160 ; Middle of the screen

My DW 100

MaxPoints EQU 125 ; Number of 3d Points

Erase DW MaxPoints DUP () ; Array for deletion screenpoints

ENDS CODE ; End of codesegment

END START ; The definite end :)

; You may use this code in your own productions but

; give credit where credit is due Only lamers steal

; code so try to create your own 3d-engine and use

; this code as an example

; Thanx must go to Arno Brouwer and Ash for releasing

; example sources

;

; Ciao dudoz,

;

; Vulture / Outlaw Triad