Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory
現在プレイした(ステージの難易度 )以上の難易度のステージをプレイ出来る． ステージ全てプレイする時に，何通りの方法があるか？ で求める．
難易度でsortして，小さい順に列に入れていく． で構成される上記のルールを満たす列に を入れることを考える．列の中に 以上のものがあれば，その後に を入れることが出来る．つまり， (までの場合の数 以上のステージの個数)通りとなる．これを 回繰り返す．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define MOD 1000000007
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
int main () {
int n , t ;
cin >> n >> t ;
vector < int > v ( n );
rep ( i , n ) cin >> v [ i ];
sort ( v . begin (), v . end ());
ll ans = 1 ;
vector < int > res ;
rep ( i , n ) {
res . push_back ( v [ i ]);
int id = lower_bound ( res . begin (), res . end (), v [ i ] - t ) - res . begin ();
ans *= ( res . size () - id );
ans %= MOD ;
}
cout << ans << endl ;
return 0 ;
}