2019-07-21  2024-09-15    514 字  2 分钟

牛客-C881 E - ABBA

假如把A看成1,B看成-1。根据它的条件会发现,他们的前缀和满足一个规律:[-m, n]。然后枚举每个位置。

可以看作是直角坐标系,原点为0。

x轴正方向看作A的数量,值为左边位置的值+1,当超出范围时置为0。

y轴正方向看作B的数量,值为下边位置的值-1,当超出范围时置为0.

其他位置均只能从左侧或下侧走到,即值为左侧加下侧的总和,当超出范围时置为0.

Code
/**
 *    author: Akvicor
 *    created: 2019-07-21 09-37-22
**/

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define prec(x) fixed << setprecision(x)
#define ms(s, n) memset(s, n, sizeof(s))
#define all(v) (v).begin(), (v).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD(x) const int MOD = (int)x + 7
#define MAXN(x) const int MAXN = (int)x + 7

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;

namespace SOL{

const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;

/**  >------- Akvicor's Solution -------< **/

MOD(1e9);
MAXN(1e6);

void mod(long long & n){ n %= (long long)MOD; }
void mod(int & n){ n %= MOD; }

LL dp[3010][3010];

void solve(){
    FAST_IO;
    
    int n, m;
    while(cin >> n >> m){
	reep(i, n+m) reep(j, n+m) dp[i][j] = 0;
	dp[0][0] = 1;
	reep(i, n+m) reep(j, n+m){
		if(i) dp[i][j] += dp[i-1][j];
		if(j) dp[i][j] += dp[i][j-1];
		//dp[i][j] %= MOD;
		mod(dp[i][j]);
		if(i-j > n || j-i > m) dp[i][j] = 0;
	}
	cout << dp[n+m][n+m] << endl;
    }
    
}

/**  >----------------------------------< **/

}

int main(){

#ifdef DEBUG
    int DEBUGCNT = 0;
    clock_t DEBUGstart, DEBUGfinish;
    double DEBUGduration;
    cout << ">------- Akvicor's Solution -------<" << endl;
DEBUGLOOP:
    DEBUGstart = clock();
#endif

    SOL::solve();

#ifdef DEBUG
    DEBUGfinish = clock();
    DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
    if(DEBUGduration > 0.07)
    cout << " --> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <--" << endl;
    ++DEBUGCNT;
    if(DEBUGCNT < 100) goto DEBUGLOOP;
    cout << ">----------------------------------<" << endl;
#endif

    return 0;
}