题意:
求n有顺序的划分为k个数的方案数.
思路:
显然这个就是一个组合公式,隔板法。可以把问题转化为x1+x2+…..xk = n 这个多元一次方程上。然后这个解就是C(n+k-1,k-1) 这道题n,k范围都是1e6。 我们可以预处理出阶乘,然后求对应的组合数,注意这里需要取Mod,用下逆元就好啦.
参考code:/* #pragma warning (disable: 4786) #pragma comment (linker, “/STACK:0x800000”) */;template< class T > T _abs(T n){return (n < 0 ? -n : n);}template< class T > T _max(T a, T b){return (!(a < b) ? a : b);}template< class T > T _min(T a, T b){return (a < b ? a : b);}template< class T > T sq(T x){return x * x;}template< class T > T gcd(T a, T b){return (b != 0 ? gcd<T>(b, a%b) : a);}template< class T > T lcm(T a, T b){return (a / gcd<T>(a, b) * b);}template< class T > bool inside(T a, T b, T c){return a<=b && b<=c;}PI = acos(-1.0);const int inf = 1<<30;const int maxn = 2e6;const int mod = 1000000007;ll fac[maxn+5];void init(){fac[0] = 1;rep(i,1,maxn) fac[i] = (fac[i-1] * i) % mod;}ll quickpow(ll m,ll n){ll ans = 1;m %= mod;while(n){if(n & 1)ans = (ans * m) % mod;n >>= 1;m = (m * m)%mod;}return ans;}ll solve(ll a, ll b, ll p){if(b > a) return 0;return fac[a] * quickpow(fac[b]*fac[a-b],p-2) % p;}int main(){//READ(“in.txt”);init();int t,kase = 1;scanf(“%d”,&t);while(t–){int n,k;scanf(“%d%d”,&n,&k);printf(“Case %d: %lld\n”,kase++,solve(n+k-1,k-1,mod));}return 0;}
，以前我是个爱仰望天空的人，苍蓝的天空总是给我求生的勇气，
