Integer Partition

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 22 Accepted Submission(s): 15

Problem Description

Given n, k, calculate the number of different (unordered) partitions of n such that no part is repeated k or more times.

Input

First line, number of test cases, T.
Following are T lines. Each line contains two numbers, n and k.

1<=n,k,T<=10⁵

Output

T lines, each line contains answer to the responding test case.
Since the numbers can be very large, you should output them modulo 10⁹+7.

Sample Input

4
4 2
4 3
4 4
4 5

Sample Output

2
4
4
5

Source

2013 Multi-University Training Contest 6

Recommend

zhuyuanchen520

跟上次多校求数的划分很类似。

所谓的五边形数定理还没有搞懂。

先贴个代码先，胡搞弄过去的

 /*

  * Author:  kuangbin

  * Created Time:  2013/8/8 11:53:35

  * File Name: 1004.cpp

  */

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <time.h>

 using namespace std;

 const int MOD = 1e9+;

 int dp[];

 void init()

 {

     memset(dp,,sizeof(dp));

     dp[] = ;

     for(int i = ;i <= ;i++)

     {

         for(int j = , r = ; i - ( * j * j - j) /  >= ; j++, r *= -)

         {

             dp[i] += dp[i -( * j * j - j) / ] * r;

             dp[i] %= MOD;

             dp[i] = (dp[i]+MOD)%MOD;

             if( i - ( * j * j + j) /  >=  )

             {

                 dp[i] += dp[i - ( * j * j + j) / ] * r;

                 dp[i] %= MOD;

                 dp[i] = (dp[i]+MOD)%MOD;

             }

         }

     }

 }

 int solve(int n,int k)

 {

     int ans = dp[n];

     for(int j = , r = -; n - k*( * j * j - j) /  >= ; j++, r *= -)

     {

         ans += dp[n -k*( * j * j - j) / ] * r;

         ans %= MOD;

         ans = (ans+MOD)%MOD;

         if( n - k*( * j * j + j) /  >=  )

         {

             ans += dp[n - k*( * j * j + j) / ] * r;

             ans %= MOD;

             ans = (ans+MOD)%MOD;

         }

     }

     return ans;

 }

 int main()

 {

     init();

     int T;

     int n,k;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&k);

         printf("%d\n",solve(n,k));

     }

     return ;

 }

巴特西

HDU 4658 Integer Partition （2013多校6 1004题）

Integer Partition

最新文章

热门文章