問題
http://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504
X[n]=X[n/p-x]+X[n/q-y]となる関数がある。
ただし、n<=0のときX[n]=1となる。
ｎが与えられたとき、X[n]がいくつになるか求める。
解き方
nは１０＾１３なので全探索では解けない。
ｄｐを利用した場合でも、10^13のメモリ空間は使えないのでメモリ量としても解くことができない。
ここで、関数の性質からnが小さいほどメモ化が有効になることが想定される。
そのため、メモリ量として保存できるだけはメモ化して、それより大きい数については単純にＤＦＳすることでメモリ量も計算量も抑えて解くことができる。
最初はmapを使っていたが動的にメモリを確保するデータ構造ではエラーが起きてしまうので、単純にlong long型で最初からメモリを確保しておく。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p,q,x,y;
long long dp[5000001];
class InfiniteSequence2 {
public:
long long f(long long n){
if(n<=0)return 1;
if(n<=5000000&&dp[n]!=0)return dp[n];
long long a=n/p-x,b=n/q-y;
a= a>0 ? f(a) : 1;
b= b>0 ? f(b) : 1;
if(n<=5000000)dp[n]=a+b;
return a+b;
}
long long calc(long long n, int p_, int q_, int x_, int y_) {
p=p_;
q=q_;
x=x_;
y=y_;
memset(dp,0,sizeof(dp));
return f(n);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p,q,x,y;
long long dp[5000001];
class InfiniteSequence2 {
public:
long long f(long long n){
if(n<=0)return 1;
if(n<=5000000&&dp[n]!=0)return dp[n];
long long a=n/p-x,b=n/q-y;
a= a>0 ? f(a) : 1;
b= b>0 ? f(b) : 1;
if(n<=5000000)dp[n]=a+b;
return a+b;
}
long long calc(long long n, int p_, int q_, int x_, int y_) {
p=p_;
q=q_;
x=x_;
y=y_;
memset(dp,0,sizeof(dp));
return f(n);
}
};