Problem Statement
Rajesh is playing a very interesting mathematical game. He has collection of sticks of length 1,2,3,....,N. He is making hexagon out of his collection by using 6 sticks for each hexagon. He considers a hexagon "good" if the biggest stick has length at least L and lengths of all the other sticks are not more than X.A "good" hexagon does not have sticks of the same length more than K times.
How many ways he can make a "Good" hexagon?
How many ways he can make a "Good" hexagon?
Input/Output Specs
Input Specification:Input contains four integers-
N( 2 <= N <= 10^9)
L ( 2 <= L <= N and N-L<=100)
X( 1<=X< L )
K ( 1 <= K <= 5)
Output Specification:
Output the number of different ways to make a "Good" hexagon% 1000000007
Input Specification:Input contains four integers-
N( 2 <= N <= 10^9)
L ( 2 <= L <= N and N-L<=100)
X( 1<=X< L )
K ( 1 <= K <= 5)
Output Specification:
Output the number of different ways to make a "Good" hexagon% 1000000007
N( 2 <= N <= 10^9)
L ( 2 <= L <= N and N-L<=100)
X( 1<=X< L )
K ( 1 <= K <= 5)
Output Specification:
Output the number of different ways to make a "Good" hexagon% 1000000007
Examples
Example:1 when N=8, L=7, X=5, K=3: { 1,2,2,5,5,7 } is a good hexagon but {1,2,2,2,2,7}, { 1,2,3,4,5,6},{1,2,3,4,6,7} are not.Two hexagons are considered different if their side length sets are different.
For example {1,2,3,4,5,6} , {1,1,1,2,2,3} and {1,1,2,2,2,3} are all different hexagons. But {1,2,3,4,5,6} and { 2,4,6,1,3,5} are not different.
Example:2 When N=10, L=8, X=6, K=2
Output: Total hexagons= 374
Note: Please return -1 for invalid cases.
/Data Structure includes
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
//Other Includes
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sf(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define fill(a,v) memset(a, v, sizeof a)
#define sz size()
#define INF (int)1e9
#define EPS 1e-9
#define bitcount __builtin_popcount
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define maX(a,b) (a>b?a:b)
#define miN(a,b) (a<b?a:b)
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long LL;
typedef pair<int, int > PII;
/*Main code begins now */
int testnum;
int len[] = {5,4,3,3,2,2,1};
int val[7][5] = { {1,1,1,1,1},
{2,1,1,1,0},
{2,2,1,0,0},
{3,1,1,0,0},
{3,2,0,0,0},
{4,1,0,0,0},
{5,0,0,0,0} };
int coeff[7][7] = { {0,60,30,20,10,5,1},
{0,0,6,6,4,3,1},
{0,0,0,0,2,1,1},
{0,0,0,0,1,2,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,0} };
int reps[] = {1,2,2,3,3,4,5};
int frac[] = {120,6,2,2,1,1,1};
LL f[7], g[7], h[7];
LL F[7], G[7], H[7];
LL acc[6];
int N,L,X,K;
const LL mod = 1000000007ll;
LL npoly[6][6] = { {1, mod-5, 10, mod-10, 5, mod-1},
{1, mod-3, 2, 2, mod-3, 1},
{1, mod-1, mod-2, 2, 1, mod-1},
{1, mod-2, 1, mod-1, 2, mod-1},
{1, 0, mod-1, mod-1, 0, 1},
{1, mod-1, 0, 0, mod-1, 1} };
pair<LL,LL> extGCD(LL a,LL b)
{
if(b==0) return mp(1ll,0ll);
else
{
pair<LL,LL> temp = extGCD(b,a%b);
return mp( temp.second, temp.first - (a/b) * temp.second);
}
}
LL inverse(LL a)
{
pair<LL,LL> temp = extGCD(a,mod);
LL x = temp.first;
while(x<0) x+=mod;
while(x>=mod) x-=mod;
return x;
}
LL nCk(LL n,LL k)
{
if(k>n/2) k=n-k;
LL num=1,den=1;
for(LL i=1;i<=k;i++)
{
num = (num*n) % mod;
den = (den*i) % mod;
n--;
}
return (num * inverse(den)) % mod;
}
/*
* 0 : (1-x)
* 1 : (1+x)
* 2 : (1+x^2)
* 3 : (1+x+x^2)
*/
LL coeffPoly(LL ind,LL n,LL k)
{
if(k<0) return 0;
if(ind==0)
return nCk(k+n-1, n-1);
if(ind==1)
{
LL ans = nCk(k+n-1, n-1);
return (k&1) ? mod-ans : ans;
}
if(ind==2)
{
assert(n==1);
LL z = k%4;
if(z==0) return 1;
if(z==1) return 0;
if(z==2) return mod-1;
if(z==3) return 0;
}
if(ind==3)
{
assert(n==1);
LL z = k%3;
if(z==0) return 1;
if(z==1) return mod-1;
if(z==2) return 0;
}
return 0;
}
LL calc(LL ind,LL S,LL N)
{
if(S<0) return 0;
LL ans=0;
if(ind==0)
{
for(int i=0;i<6;i++)
{
//printf("%lldn",S-N*i);
ans = (ans + (coeffPoly(0,6,S-N*i) * npoly[0][i])) % mod;
}
return ans;
}
if(ind==1)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term1 = (coeffPoly(1,1,K) * inverse(32)) % mod;
LL term21 = (coeffPoly(0,5,K) * (31)) % mod;
LL term22 = (coeffPoly(0,5,K-1) * (mod-26)) % mod;
LL term23 = (coeffPoly(0,5,K-2) * (16)) % mod;
LL term24 = (coeffPoly(0,5,K-3) * (mod-6)) % mod;
LL term25 = (coeffPoly(0,5,K-4) * (1)) % mod;
LL term2 = ((term21+term22+term23+term24+term25) * inverse(32)) % mod;
ans = (ans + (term1+term2) * npoly[1][i]) % mod;
}
return ans;
}
if(ind==2)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term11 = (coeffPoly(1,2,K) * (3)) % mod;
LL term12 = (coeffPoly(1,2,K-1) * (2)) % mod;
LL term1 = ((term11+term12) * inverse(16)) % mod;
LL term21 = (coeffPoly(0,4,K) * (13)) % mod;
LL term22 = (coeffPoly(0,4,K-1) * (mod-16)) % mod;
LL term23 = (coeffPoly(0,4,K-2) * (9)) % mod;
LL term24 = (coeffPoly(0,4,K-3) * (mod-2)) % mod;
LL term2 = ((term21+term22+term23+term24) * inverse(16)) % mod;
ans = (ans + (term1+term2) * npoly[2][i]) % mod;
}
return ans;
}
if(ind==3)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term1 = (coeffPoly(3,1,K-1) * inverse(9)) % mod;
LL term21 = (coeffPoly(0,4,K) * (9)) % mod;
LL term22 = (coeffPoly(0,4,K-1) * (mod-10)) % mod;
LL term23 = (coeffPoly(0,4,K-2) * (5)) % mod;
LL term24 = (coeffPoly(0,4,K-3) * (mod-1)) % mod;
LL term2 = ((term21+term22+term23+term24) * inverse(9)) % mod;
ans = (ans + (term1+term2) * npoly[3][i]) % mod;
}
return ans;
}
if(ind==4)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term11 = (coeffPoly(3,1,K) * (2)) % mod;
LL term12 = (coeffPoly(3,1,K-1) * (1)) % mod;
LL term1 = ((term11+term12) * inverse(9)) % mod;
LL term21 = (coeffPoly(0,3,K) * (47)) % mod;
LL term22 = (coeffPoly(0,3,K-1) * (mod-52)) % mod;
LL term23 = (coeffPoly(0,3,K-2) * (17)) % mod;
LL term2 = ((term21+term22+term23) * inverse(72)) % mod;
LL term3 = (coeffPoly(1,1,K) * inverse(8)) % mod;
ans = (ans + (term1+term2+term3) * npoly[4][i]) % mod;
}
return ans;
}
if(ind==5)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term1 = (coeffPoly(2,1,K-1) * inverse(4)) % mod;
LL term21 = (coeffPoly(0,3,K) * (15)) % mod;
LL term22 = (coeffPoly(0,3,K-1) * (mod-16)) % mod;
LL term23 = (coeffPoly(0,3,K-2) * (5)) % mod;
LL term2 = ((term21+term22+term23) * inverse(16)) % mod;
LL term3 = (coeffPoly(1,1,K) * inverse(16)) % mod;
ans = (ans + (term1+term2+term3) * npoly[5][i]) % mod;
}
return ans;
}
if(ind==6)
{
return min(N, 1 + S/5);
}
}
LL calcD(LL ind,LL S,LL X)
{
LL cnt=0;
S-=5;
/*
for(int a1=0; a1<X; a1+=val[ind][0])
{ if(len[ind]==1 && a1<=S) cnt++;
else if(a1>S) break;
else if(len[ind]>1)
for(int a2=0; a2<X; a2+=val[ind][1])
{ if(len[ind]==2 && a1+a2<=S) cnt++;
else if(a1+a2>S) break;
else if(len[ind]>2)
for(int a3=0; a3<X; a3+=val[ind][2])
{ if(len[ind]==3 && a1+a2+a3<=S) cnt++;
else if(a1+a2+a3>S) break;
else if(len[ind]>3)
for(int a4=0; a4<X; a4+=val[ind][3])
{ if(len[ind]==4 && a1+a2+a3+a4<=S) cnt++;
else if(a1+a2+a3+a4>S) break;
else if(len[ind]>4)
for(int a5=0; a5<X; a5+=val[ind][4])
{ if(len[ind]==5 && a1+a2+a3+a4+a5<=S) cnt++;
else if(a1+a2+a3+a4+a5>S) break;
}}}}}
*/
LL z = calc(ind,S,X);
//printf("%lld , %lld , %lld : %lldn", ind, S, X, z);
return z;
}
LL power(LL x,LL n)
{
LL ans=1;
while(n)
{
if(n&1) ans = (ans*x)%mod;
x = (x*x)%mod;
n >>= 1;
}
return ans;
}
void preprocess()
{
}
void solve()
{
fill(f,0); fill(g,0); fill(h,0);
fill(F,0); fill(G,0); fill(H,0);
fill(acc,0);
for(int S=L;S<=N;S++)
{
for(int i=0;i<7;i++)
{
f[i] = calcD(i,S,X);
F[i] = power(X,len[i]);
//printf("Sum = %d : i=%d, %lld, %lldn",S,i,f[i],F[i]);
}
for(int i=6;i>=0;i--)
{
g[i]=f[i];
G[i]=F[i];
for(int j=0;j<7;j++)
{
g[i] = (g[i] + mod - (coeff[i][j]*h[j])%mod ) % mod;
G[i] = (G[i] + mod - (coeff[i][j]*H[j])%mod ) % mod;
}
h[i] = (g[i] * inverse(frac[i])) % mod;
H[i] = (G[i] * inverse(frac[i])) % mod;
acc[ reps[i] ] = (acc[reps[i]] + mod + H[i]-h[i]) % mod;
//printf("H values %d : %lld %lldn",i,H[i],h[i]);
}
}
LL sum=0;
for(int i=1;i<6;i++)
{
if(i<=K)
sum = (sum + acc[i]) % mod;
//printf("%d : %lldn",i,acc[i]);
}
cout<<sum<<endl;
}
bool input()
{
s(N) ;s(L); s(X); s(K);
return true;
}
int main()
{
preprocess();
int T=1;
for(testnum=1;testnum<=T;testnum++)
{
if(!input()) break;
solve();
}
}
Example:1 when N=8, L=7, X=5, K=3: { 1,2,2,5,5,7 } is a good hexagon but {1,2,2,2,2,7}, { 1,2,3,4,5,6},{1,2,3,4,6,7} are not.Two hexagons are considered different if their side length sets are different.
For example {1,2,3,4,5,6} , {1,1,1,2,2,3} and {1,1,2,2,2,3} are all different hexagons. But {1,2,3,4,5,6} and { 2,4,6,1,3,5} are not different.
Example:2 When N=10, L=8, X=6, K=2
Output: Total hexagons= 374
Note: Please return -1 for invalid cases.
For example {1,2,3,4,5,6} , {1,1,1,2,2,3} and {1,1,2,2,2,3} are all different hexagons. But {1,2,3,4,5,6} and { 2,4,6,1,3,5} are not different.
Example:2 When N=10, L=8, X=6, K=2
Output: Total hexagons= 374
Note: Please return -1 for invalid cases.
/Data Structure includes
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
//Other Includes
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sf(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define fill(a,v) memset(a, v, sizeof a)
#define sz size()
#define INF (int)1e9
#define EPS 1e-9
#define bitcount __builtin_popcount
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define maX(a,b) (a>b?a:b)
#define miN(a,b) (a<b?a:b)
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long LL;
typedef pair<int, int > PII;
/*Main code begins now */
int testnum;
int len[] = {5,4,3,3,2,2,1};
int val[7][5] = { {1,1,1,1,1},
{2,1,1,1,0},
{2,2,1,0,0},
{3,1,1,0,0},
{3,2,0,0,0},
{4,1,0,0,0},
{5,0,0,0,0} };
int coeff[7][7] = { {0,60,30,20,10,5,1},
{0,0,6,6,4,3,1},
{0,0,0,0,2,1,1},
{0,0,0,0,1,2,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,0} };
int reps[] = {1,2,2,3,3,4,5};
int frac[] = {120,6,2,2,1,1,1};
LL f[7], g[7], h[7];
LL F[7], G[7], H[7];
LL acc[6];
int N,L,X,K;
const LL mod = 1000000007ll;
LL npoly[6][6] = { {1, mod-5, 10, mod-10, 5, mod-1},
{1, mod-3, 2, 2, mod-3, 1},
{1, mod-1, mod-2, 2, 1, mod-1},
{1, mod-2, 1, mod-1, 2, mod-1},
{1, 0, mod-1, mod-1, 0, 1},
{1, mod-1, 0, 0, mod-1, 1} };
pair<LL,LL> extGCD(LL a,LL b)
{
if(b==0) return mp(1ll,0ll);
else
{
pair<LL,LL> temp = extGCD(b,a%b);
return mp( temp.second, temp.first - (a/b) * temp.second);
}
}
LL inverse(LL a)
{
pair<LL,LL> temp = extGCD(a,mod);
LL x = temp.first;
while(x<0) x+=mod;
while(x>=mod) x-=mod;
return x;
}
LL nCk(LL n,LL k)
{
if(k>n/2) k=n-k;
LL num=1,den=1;
for(LL i=1;i<=k;i++)
{
num = (num*n) % mod;
den = (den*i) % mod;
n--;
}
return (num * inverse(den)) % mod;
}
/*
* 0 : (1-x)
* 1 : (1+x)
* 2 : (1+x^2)
* 3 : (1+x+x^2)
*/
LL coeffPoly(LL ind,LL n,LL k)
{
if(k<0) return 0;
if(ind==0)
return nCk(k+n-1, n-1);
if(ind==1)
{
LL ans = nCk(k+n-1, n-1);
return (k&1) ? mod-ans : ans;
}
if(ind==2)
{
assert(n==1);
LL z = k%4;
if(z==0) return 1;
if(z==1) return 0;
if(z==2) return mod-1;
if(z==3) return 0;
}
if(ind==3)
{
assert(n==1);
LL z = k%3;
if(z==0) return 1;
if(z==1) return mod-1;
if(z==2) return 0;
}
return 0;
}
LL calc(LL ind,LL S,LL N)
{
if(S<0) return 0;
LL ans=0;
if(ind==0)
{
for(int i=0;i<6;i++)
{
//printf("%lldn",S-N*i);
ans = (ans + (coeffPoly(0,6,S-N*i) * npoly[0][i])) % mod;
}
return ans;
}
if(ind==1)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term1 = (coeffPoly(1,1,K) * inverse(32)) % mod;
LL term21 = (coeffPoly(0,5,K) * (31)) % mod;
LL term22 = (coeffPoly(0,5,K-1) * (mod-26)) % mod;
LL term23 = (coeffPoly(0,5,K-2) * (16)) % mod;
LL term24 = (coeffPoly(0,5,K-3) * (mod-6)) % mod;
LL term25 = (coeffPoly(0,5,K-4) * (1)) % mod;
LL term2 = ((term21+term22+term23+term24+term25) * inverse(32)) % mod;
ans = (ans + (term1+term2) * npoly[1][i]) % mod;
}
return ans;
}
if(ind==2)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term11 = (coeffPoly(1,2,K) * (3)) % mod;
LL term12 = (coeffPoly(1,2,K-1) * (2)) % mod;
LL term1 = ((term11+term12) * inverse(16)) % mod;
LL term21 = (coeffPoly(0,4,K) * (13)) % mod;
LL term22 = (coeffPoly(0,4,K-1) * (mod-16)) % mod;
LL term23 = (coeffPoly(0,4,K-2) * (9)) % mod;
LL term24 = (coeffPoly(0,4,K-3) * (mod-2)) % mod;
LL term2 = ((term21+term22+term23+term24) * inverse(16)) % mod;
ans = (ans + (term1+term2) * npoly[2][i]) % mod;
}
return ans;
}
if(ind==3)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term1 = (coeffPoly(3,1,K-1) * inverse(9)) % mod;
LL term21 = (coeffPoly(0,4,K) * (9)) % mod;
LL term22 = (coeffPoly(0,4,K-1) * (mod-10)) % mod;
LL term23 = (coeffPoly(0,4,K-2) * (5)) % mod;
LL term24 = (coeffPoly(0,4,K-3) * (mod-1)) % mod;
LL term2 = ((term21+term22+term23+term24) * inverse(9)) % mod;
ans = (ans + (term1+term2) * npoly[3][i]) % mod;
}
return ans;
}
if(ind==4)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term11 = (coeffPoly(3,1,K) * (2)) % mod;
LL term12 = (coeffPoly(3,1,K-1) * (1)) % mod;
LL term1 = ((term11+term12) * inverse(9)) % mod;
LL term21 = (coeffPoly(0,3,K) * (47)) % mod;
LL term22 = (coeffPoly(0,3,K-1) * (mod-52)) % mod;
LL term23 = (coeffPoly(0,3,K-2) * (17)) % mod;
LL term2 = ((term21+term22+term23) * inverse(72)) % mod;
LL term3 = (coeffPoly(1,1,K) * inverse(8)) % mod;
ans = (ans + (term1+term2+term3) * npoly[4][i]) % mod;
}
return ans;
}
if(ind==5)
{
for(int i=0;i<6;i++)
{
LL K = S-N*i;
LL term1 = (coeffPoly(2,1,K-1) * inverse(4)) % mod;
LL term21 = (coeffPoly(0,3,K) * (15)) % mod;
LL term22 = (coeffPoly(0,3,K-1) * (mod-16)) % mod;
LL term23 = (coeffPoly(0,3,K-2) * (5)) % mod;
LL term2 = ((term21+term22+term23) * inverse(16)) % mod;
LL term3 = (coeffPoly(1,1,K) * inverse(16)) % mod;
ans = (ans + (term1+term2+term3) * npoly[5][i]) % mod;
}
return ans;
}
if(ind==6)
{
return min(N, 1 + S/5);
}
}
LL calcD(LL ind,LL S,LL X)
{
LL cnt=0;
S-=5;
/*
for(int a1=0; a1<X; a1+=val[ind][0])
{ if(len[ind]==1 && a1<=S) cnt++;
else if(a1>S) break;
else if(len[ind]>1)
for(int a2=0; a2<X; a2+=val[ind][1])
{ if(len[ind]==2 && a1+a2<=S) cnt++;
else if(a1+a2>S) break;
else if(len[ind]>2)
for(int a3=0; a3<X; a3+=val[ind][2])
{ if(len[ind]==3 && a1+a2+a3<=S) cnt++;
else if(a1+a2+a3>S) break;
else if(len[ind]>3)
for(int a4=0; a4<X; a4+=val[ind][3])
{ if(len[ind]==4 && a1+a2+a3+a4<=S) cnt++;
else if(a1+a2+a3+a4>S) break;
else if(len[ind]>4)
for(int a5=0; a5<X; a5+=val[ind][4])
{ if(len[ind]==5 && a1+a2+a3+a4+a5<=S) cnt++;
else if(a1+a2+a3+a4+a5>S) break;
}}}}}
*/
LL z = calc(ind,S,X);
//printf("%lld , %lld , %lld : %lldn", ind, S, X, z);
return z;
}
LL power(LL x,LL n)
{
LL ans=1;
while(n)
{
if(n&1) ans = (ans*x)%mod;
x = (x*x)%mod;
n >>= 1;
}
return ans;
}
void preprocess()
{
}
void solve()
{
fill(f,0); fill(g,0); fill(h,0);
fill(F,0); fill(G,0); fill(H,0);
fill(acc,0);
for(int S=L;S<=N;S++)
{
for(int i=0;i<7;i++)
{
f[i] = calcD(i,S,X);
F[i] = power(X,len[i]);
//printf("Sum = %d : i=%d, %lld, %lldn",S,i,f[i],F[i]);
}
for(int i=6;i>=0;i--)
{
g[i]=f[i];
G[i]=F[i];
for(int j=0;j<7;j++)
{
g[i] = (g[i] + mod - (coeff[i][j]*h[j])%mod ) % mod;
G[i] = (G[i] + mod - (coeff[i][j]*H[j])%mod ) % mod;
}
h[i] = (g[i] * inverse(frac[i])) % mod;
H[i] = (G[i] * inverse(frac[i])) % mod;
acc[ reps[i] ] = (acc[reps[i]] + mod + H[i]-h[i]) % mod;
//printf("H values %d : %lld %lldn",i,H[i],h[i]);
}
}
LL sum=0;
for(int i=1;i<6;i++)
{
if(i<=K)
sum = (sum + acc[i]) % mod;
//printf("%d : %lldn",i,acc[i]);
}
cout<<sum<<endl;
}
bool input()
{
s(N) ;s(L); s(X); s(K);
return true;
}
int main()
{
preprocess();
int T=1;
for(testnum=1;testnum<=T;testnum++)
{
if(!input()) break;
solve();
}
}
No comments:
Post a Comment