题目描述

blablabla

样例

blablabla

算法1

(记忆化搜索)

C++ 代码

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int mod = 1e4+7;
int n,m,k,a,b;
int f[1001][1001];//一个存y的系数，另一个存当前是几次方
int dfs(int x,int y,int t);

void solve(){
    read(a);read(b);read(k);read(n);read(m);
    a%=mod;
    b%=mod;
    write(dfs(n,m,k)%mod);
    pc('\n');
}
signed main(){
    solve();
    return 0;
}
int dfs(int x,int y,int t){
    //if(f[y][t])return f[y][t];
    if(x>t||y>t)return 0;
    if(t == 1){
        if(x == 1&&!y)return f[y][t]=a;
        else if(!x&&y==1)return f[y][t]=b;
        return 0;
    }
    if(f[y][t])return f[y][t];
    int ans = dfs(x,y-1,t-1);//递归的进行寻找
    ans%=mod;
    ans *= b;
    ans %= mod;
    int sum = 0;
    sum = dfs(x-1,y,t-1);
    sum *= a;
    ans += sum;
    ans %=mod;
    return f[y][t] =  ans%mod;
}