AtCoder Grand Contest 025 B - RGB Coloring

組み合わせで独立は典型！(ﾌﾞｵﾝｯ!)
組み合わせで独立は典型！(ﾌﾞｵﾝｯ!)
組み合わせで独立は典型！(ﾌﾞｵﾝｯ!)
組み合わせで独立は典型！(ﾌﾞｵﾝｯ!)

問題

B - RGB Coloring

感想

Ax + By = K を満たすx,yそれぞれについて計算をしたくなるのですが(ﾌﾞｵﾝｯ!)
それがなかなか出せないんですよね(ﾌﾞｵﾝｯ!)

順位表を見るとかなりの人が高速で通しているので(ﾌﾞｵﾝｯ!)、考察ステップは少なそうな気はしていましたが(ﾌﾞｵﾝｯ!)

変にはまってちゃいましたね！(ﾌﾞｵﾝｯ!)反省だ！！！(ﾌﾞｵﾝｯ!)


ふぅ…

(追記)

えー、流石に適当すぎましたね。

まあ、ほとんどこれで終わりなきもしますが。

さてさて、いきなりですが問題をこう言い換えてみます

二次元座標上の行動について考える。
最初は原点にいる
以下の4つのうち、いずれかの行為を合計でｎ回行う

  • x軸の正の方向へAだけ移動する
  • y軸の正の方向へBだけ移動する
  • x軸の正の方向へAだけ移動した後、y軸の正の方向へBだけ移動ずる
  • 移動せずその場にとどまる

この行動が終了したときに原点からのマンハッタン距離がKの所にいる場合の組み合わせを答えよ。

問題設定いろいろとガバガバですが、お気持ちを汲み取ってくださいｗ
この問題だと、xとyを分けたくなりませんか？
二次元座標上での行動について、xとyを分けるというのは結構しみわたっている話な気がします。

この話についても、今回の組み合わせについても、もともとは
「複数の操作について同時に考えるのはむつかしいので独立して考える。」というものです。

操作を最初に整理できないかというのは考えるべきなんですよね。
ここまで行くと、なーんだ、簡単じゃん(解けませんでしたが)ってなりませんか。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

//ａをbで割る
long long mod_div(ll a,ll b){
	if(a % b == 0)return a/b;
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}

#define MAX_K 333333
vector<long long> kaijo(MAX_K);
long long combination(long long n, long long r){
    if(n < r || n < 0 || r < 0)
        return 0;
	if(kaijo[0] != 1){
		kaijo[0] = 1;
		for(long long i = 1;i < MAX_K;i++)kaijo[i] = (kaijo[i-1] * i) % MOD;
	}
    long long ret = kaijo[n];
	long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
    return mod_div(ret,tmp);
}

int main(){
	ll n,a,b,k;cin >> n >> a >> b >> k;
	ll ans = 0;
	for(ll i = 0;i <= n;i++){
		if((k-a*i) % b == 0){
			ll j = (k-a*i)/b;
			if(j > n)continue;
			ans += combination(n,i)*combination(n,j)%MOD;
			ans %= MOD;
		}
	}
	cout << ans << endl;

	return 0;
}


実装も軽いね。
うーんって感じだ(全く解説してないけれど放送見ると一発なので)

そういえば、MODの計算について、毎回悩みましたが、割り算とコンビネーションだけ持つことにしました。
クラスを用意(というかうまい人々のをお借り)していましたが、あまりしっくりこなかったのでね。