The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ 3742 Equivalent Polynomial java

开始自己写个C(n,m) RE... 后来改成递推 AC...
另外就是while里面一定要用while(cin.hasNext)???不能用cin.hasNextInt()???用了就RE...丫的。。。

import java.math.BigInteger;
import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static BigInteger t=new BigInteger("1");
    static BigInteger c[][] = new BigInteger [210][210];

    /*
    static BigInteger C(int n,int m)
    {
        if(m==0||m==n)
            return BigInteger.ONE;
        BigInteger res=new BigInteger("1");
        int i;
        for(i=n;i>=n-m+1;i--)
            res=res.multiply(BigInteger.valueOf(i));
        for(i=m;i>=1;i--)
            res=res.divide(BigInteger.valueOf(i));
        return res;
    }
    */

    static int a[]=new int[202];
    static BigInteger ans[]=new BigInteger [202];

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        for(int i=0;i<=200;i++) c[i][0]=c[i][i]=BigInteger.ONE;
        for(int i=2;i<=200;i++)
        {
            for(int j=1;j<i;j++)
            {
                c[i][j]=c[i-1][j].add(c[i-1][j-1]);
            }
        }
        Scanner cin = new Scanner (new BufferedInputStream(System.in));
        while(cin.hasNext())
        {

            n=cin.nextInt();
            t=cin.nextBigInteger();
            int i,j;
            for(i=0;i<=n;i++)
                a[i]=cin.nextInt();
            for(i=0;i<=n;i++)
                ans[i]=BigInteger.ZERO;

            for(i=0;i<=n;i++)
                for(j=i;j<=n;j++)
                   if(j-i<i)
                    ans[i]=ans[i].add(c[j][j-i].multiply(t.pow(j-i)).multiply(BigInteger.valueOf(a[j])));
                   else
                    ans[i]=ans[i].add(c[j][i].multiply(t.pow(j-i)).multiply(BigInteger.valueOf(a[j])));
            for(i=0;i<n;i++)
            {
                System.out.print(ans[i]);
                System.out.print(" ");
            }
             System.out.println(ans[n]);

            /*
            String res=new String ("");
            for(i=0;i<n;i++)
            {
                res+=ans[i].toString();
                res+=" ";
            }
            res+=ans[n].toString();
            System.out.print(res);
            System.out.println();
             * */

       }
 
    }
}

posted on 2010-04-23 12:57 abilitytao 阅读(1010) 评论(1)  编辑 收藏 引用

评论

# re: POJ 3742 Equivalent Polynomial java 2010-04-24 09:11 乐蜂网购物网站

这些常年在现场  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理