2015
09-17

Integer Partition

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

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

1<=n,k,T<=105

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

1<=n,k,T<=105

4
4 2
4 3
4 4
4 5

2
4
4
5

P(x)*phi(x)=1  -> p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)……=0

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100000
#define mod 1000000007
#define ll long long
ll p[N+10];

void init()
{
p[0]=p[1]=1;
for(int i=2;i<=N;++i)
{
p[i]=0;int x=1;
for(int k=1,j=1;x>=0;++k,j*=-1)
{
x=i-(3*k*k+k)/2;
if(x>=0) p[i]+=p[x]*j;
x=i-(3*k*k-k)/2;
if(x>=0) p[i]+=p[x]*j;
if(p[i]>=mod||p[i]<0)
p[i]=(p[i]%mod+mod)%mod;
}
}
}

int main ()
{
init();
int T;scanf("%d",&T);
while(T--)
{
int n,K;
scanf("%d%d",&n,&K);
ll ans=p[n];
int x=1;
for(int k=1,j=-1;x>=0;++k,j*=-1)
{
x=n-(3*k*k+k)/2*K;
if(x>=0) ans+=p[x]*j;
x=n-(3*k*k-k)/2*K;
if(x>=0) ans+=p[x]*j;
if(ans>=mod||ans<0)
ans=(ans%mod+mod)%mod;
}
printf("%I64d\n",ans);
}
return 0;
}



1. ᓁᓁᓁᓁᓁᓁᓁᓁ丝袜女人ᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁ黑色透明丝袜ᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁᓁ古力娜扎t台展美腿ᓁᓁᓁᓁᓁᓁᓁᓁhTtP://6637.meizi1.com