一．数学作业

这道题要求求x1+2x2+……+nxn=m（n,m为输入数据）的解集的个数；

一开始我想用DP，f[i,j,m]=sum{f[i,k,q]+f[k,j,m-q]},但样例都过不了。

后来想到了背包，但一时没有转过弯，以前做的背包都把物品价值给出了的，但这次却让我求价值（耸肩）。

Std就是用的完全背包，把1……n当作每个物品的价值，然后求个数使得刚好装满背包。状态转移方程：f[i,j]=f[i-1,j]+f[i-1,j-i]。即决定第i件物品装不装入。可变为一维数组f[j]=(f[j]+f[j-i])%1000000000;

二．求n!后有多少0

一个数的阶乘里要出现后缀0，则必须要有2*5，2肯定是要比5多的，即要求1*2……*n里可以分出多少个5；

1.可以用DP；f[1]=0;f[i]=f[i-1]+i里的5的个数

2.5的个数=(i/5)+(i/5/5)+……;

Eg：100/5+100/5/5(=4<5)=24;(原理不知（耸肩）)；

二分答案加SPFA，从1~100000开始二分，然后SPFA，比mid大的设为1，否则设为0，然后求最短路，若比k大则往右边二分，否则往左边二分。