codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<iostream> #include<vector> #include<string> #include<set> #include<map> #include<queue> #include<stack> #include<utility> #include<algorithm> #include<numeric> #include<functional> #include<utility> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cctype> #include<cmath> using namespace std; #define FOR(i,a,n) for(int i = (int)(a); i < (int)(n); ++i) #define REP(i,n) FOR(i,0,n) #define FOR_EACH(i,v) for(__typeof((v).begin())i=(v).begin(); i!=(v).end(); ++i) #define ALL(v) (v).begin(), (v).end() #define MP make_pair #define PB push_back const long long mod(1051962371); long long tab[101][101][2]; #define EXIST 1 #define NOHERE 0 //間違えたグラスを取ったら、 //1,新しい間違え連鎖を作り、今取ったグラスが本来なら正解な人?のところへ行く //2,間違えの連鎖を閉じる //の二つの可能性を考える。最終的にはこんなイメージ // 人 1 2 3 4 5 6 7 8 9 10 // グラス 2 3 1 4 5 7 8 9 6 10 // 正否 n n n y y n n n n y //今間違えたグラスを本来割り当てるべき人、を次のターゲットにして関数を潜ってく long long dfs(int G, int C, int idx = 0, int correct = 0, int exist_correct = EXIST){ if(tab[idx][correct][exist_correct] >= 0) return tab[idx][correct][exist_correct]; if(idx >= G){ return C <= correct ? 1 : 0; } long long& ret = tab[idx][correct][exist_correct]; ret = 0; if(exist_correct == EXIST){ //正解グラスがあるので正解グラスを取った場合 ret = dfs(G, C, idx+1, correct+1, EXIST) % mod; }else{ //正解グラスがどこかで使われた状態なので、間違えグループを閉じる ret = (ret + dfs(G, C, idx+1, correct, EXIST)) % mod; } //新しい間違え連鎖を作る or 今の間違え連鎖を継続する if(idx < G-1) ret = (ret + dfs(G, C, idx+1, correct, NOHERE) % mod * max(1, G-(idx+1))) % mod; // cerr << idx << " " << correct << " " << exist_correct << " " << ret << endl; return ret; } int main(){ int N; cin >> N; while(N --> 0){ memset(tab, -1, sizeof(tab)); int G, C; cin >> G >> C; cout << dfs(G, C) << endl; } return 0; }
Private
[
?
]
Run code
Submit