Category : DP, PIE, Probability
Solution:
First I will discuss DP solution.
Let f(x) = # of expected move to achieve x different coupons.
We know already f(0), f(1)…. ,f(x-1);
Now To achieve x different moves, Lets consider a coupon. We have two case
The coupons is one of the x-1 of f(x-1)
This could be different from the x-1 of f(x-1)
This lead us to a dp solution .
This leads us to a closed form
code :
//
// main.cpp
// 10288 - Coupons
//
// Created by Repon Macbook on 12/28/15.
// Copyright © 2015 Repon Macbook. All rights reserved.
//
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < (n) ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
int len(Long n)
{
int cnt = 0;
while(n){
cnt ++;
n/=10;
}
return cnt;
}
class Frac {
public:
long long a, b;
Frac() {
a = 0, b = 1;
}
Frac(long long x, long long y) {
a = x, b = y;
reduce();
}
Frac operator+(const Frac &y) {
long long ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) + y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator-(const Frac &y) {
long long ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) - y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator*(const Frac &y) {
long long tx, ty, tz, tw, g;
tx = this->a, ty = y.b;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.a;
g = gcd(tz, tw), tz /= g, tw /= g;
Frac z(tx*tw, ty*tz);
return z;
}
Frac operator/(const Frac &y) {
long long tx, ty, tz, tw, g;
tx = this->a, ty = y.a;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.b;
g = gcd(tz, tw), tz /= g, tw /= g;
Frac z(tx*tw, ty*tz);
return z;
}
void print()
{
if(b==1) {
printf("%lld\n", a);
}else {
Long o = a/b;
Long d = a%b;
int pad = len(o);
int dag = len(b);
if(o) {
forn(i,pad+1) printf(" ");
printf("%lld\n", d);
printf("%lld ",o);
forn(i,dag) printf("-");
printf("\n");
forn(i,pad+1) printf(" ");
printf("%lld\n",b);
}else {
printf("%lld\n",d);
forn(i,dag) printf(" ");
printf("%lld\n",b);
}
}
}
private:
static long long gcd(long long x, long long y) {
if(!y) return x;
if(x < 0) x *= -1;
if(y < 0) y *= -1;
long long t;
while(x%y)
t = x, x = y, y = t%y;
return y;
}
void reduce() {
long long g = gcd(a, b);
a /= g, b /= g;
if(b < 0) a *= -1, b *= -1;
}
};
/*************************** END OF TEMPLATE ****************************/
const int N = 1001;
int n;
int main()
{
Frac ans;
while(scanf("%d",&n)==1) {
ans = {0,1};
for(int i= 1;i <=n; i ++ ) {
ans = ans + Frac(n,n-i+1);
}
ans.print();
}
return 0;
}
Another solution is using Principal of Inclusion-Exclusion.
The formula is :
Using this is really easy.
code :
//
// main.cpp
// 10288 - Coupons
//
// Created by Repon Macbook on 12/28/15.
// Copyright © 2015 Repon Macbook. All rights reserved.
//
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < (n) ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
int len(Long n)
{
int cnt = 0;
while(n){
cnt ++;
n/=10;
}
return cnt;
}
class Frac {
public:
long long a, b;
Frac() {
a = 0, b = 1;
}
Frac(long long x, long long y) {
a = x, b = y;
reduce();
}
Frac operator+(const Frac &y) {
long long ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) + y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator-(const Frac &y) {
long long ta, tb;
tb = this->b/gcd(this->b, y.b)*y.b;
ta = this->a*(tb/this->b) - y.a*(tb/y.b);
Frac z(ta, tb);
return z;
}
Frac operator*(const Frac &y) {
long long tx, ty, tz, tw, g;
tx = this->a, ty = y.b;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.a;
g = gcd(tz, tw), tz /= g, tw /= g;
Frac z(tx*tw, ty*tz);
return z;
}
Frac operator/(const Frac &y) {
long long tx, ty, tz, tw, g;
tx = this->a, ty = y.a;
g = gcd(tx, ty), tx /= g, ty /= g;
tz = this->b, tw = y.b;
g = gcd(tz, tw), tz /= g, tw /= g;
Frac z(tx*tw, ty*tz);
return z;
}
void print()
{
if(b==1) {
printf("%lld\n", a);
}else {
Long o = a/b;
Long d = a%b;
int pad = len(o);
int dag = len(b);
if(o) {
forn(i,pad+1) printf(" ");
printf("%lld\n", d);
printf("%lld ",o);
forn(i,dag) printf("-");
printf("\n");
forn(i,pad+1) printf(" ");
printf("%lld\n",b);
}else {
printf("%lld\n",d);
forn(i,dag) printf(" ");
printf("%lld\n",b);
}
}
}
private:
static long long gcd(long long x, long long y) {
if(!y) return x;
if(x < 0) x *= -1;
if(y < 0) y *= -1;
long long t;
while(x%y)
t = x, x = y, y = t%y;
return y;
}
void reduce() {
long long g = gcd(a, b);
a /= g, b /= g;
if(b < 0) a *= -1, b *= -1;
}
};
/*************************** END OF TEMPLATE ****************************/
const int N = 1001;
int n;
Long comb[40][40];
void f()
{
for(int i = 0; i < 34; i ++ ) {
comb[i][0] = 1;
for(int j = 1;j <=i; j ++ ) {
comb[i][j]= comb[i-1][j] + comb[i-1][j-1];
}
}
}
int main()
{
f();
Frac ans;
while(scanf("%d",&n)==1) {
ans = {0,1};
for(int i = 1;i <= n; i ++ ) {
if(i&1)ans = ans + Frac(n*comb[n][i], i);
else ans =ans- Frac(n*comb[n][i], i);
}
ans.print();
}
return 0;
}
as the set of points `P` such that:
). 
to the circle formula and manipulate to get:
Code for Fun 