poj 2515 差分序列,排列组合

大神博客链接 http://blog.csdn.net/kksleric/article/details/8021276

这道题的差分序列从没看过，公式题。

先构造从0到m的第p阶差分序列，算出0^p,1^p,...,p^p,填入表的第一行；

然后前向差分，求出以下所有(p-1)~1阶部分的差分表，差分表的最左边一竖行记作C0、C1...Cp。

令C[n+1][1]=n,用递推构造C[n+1][1]~C[n+1][p+1]的组合数打个一维表C[]；

最后利用C0*C[1]+C1*C[2]+...+Cp*C[p+1]得出答案...

Orz

 

import java.io.PrintWriter; import java.math.BigInteger; import java.util.Scanner;public class Main {Scanner scan=new Scanner(System.in);PrintWriter out=new PrintWriter(System.out);BigInteger c[]=new BigInteger[105];BigInteger h[][]=new BigInteger[105][105];BigInteger n,re;int m;void getc(){c[1]=n;for(int i=2;i<=m+1;i++)c[i]=c[i-1].multiply(n.subtract(BigInteger.valueOf(i-1))).divide(BigInteger.valueOf(i));}void run(){int cas=scan.nextInt();while(cas-- >0){n=scan.nextBigInteger().add(BigInteger.ONE);m=scan.nextInt();getc();for(int i=0;i<=m;i++)h[0][i]=BigInteger.valueOf(i).pow(m);for(int i=1;i<=m;i++)for(int j=0;j<=m-i;j++)h[i][j]=h[i-1][j+1].subtract(h[i-1][j]);re=BigInteger.ZERO;for(int i=0;i<=m;i++)re=re.add(c[i+1].multiply(h[i][0]));out.println(re);out.flush();}}public static void main(String[] args) {new Main().run();} }

 

转载于:https://www.cnblogs.com/acmicky/p/3351862.html

总结

以上是生活随笔为你收集整理的poj 2515 差分序列,排列组合的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。