提出番号 | 2394 |
---|---|

提出者 | kya |

言語 | C++ |

提出日時 | 2020-04-29 18:48:15 |

問題名 | (71)音楽ゲーム |

結果 | AC |

点数 | 100% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | AC | 100% | 13ms | 7792KB |

2 | AC | 100% | 10ms | 8464KB |

3 | AC | 100% | 10ms | 8432KB |

4 | AC | 100% | 23ms | 7824KB |

5 | AC | 100% | 18ms | 7648KB |

6 | AC | 100% | 22ms | 8560KB |

7 | AC | 100% | 3ms | 7904KB |

8 | AC | 100% | 23ms | 7616KB |

9 | AC | 100% | 32ms | 7856KB |

10 | AC | 100% | 22ms | 7728KB |

11 | AC | 100% | 24ms | 8512KB |

12 | AC | 100% | 41ms | 8464KB |

13 | AC | 100% | 12ms | 7840KB |

14 | AC | 100% | 34ms | 8544KB |

15 | AC | 100% | 8ms | 8448KB |

16 | AC | 100% | 4ms | 7888KB |

17 | AC | 100% | 44ms | 7616KB |

18 | AC | 100% | 32ms | 7888KB |

19 | AC | 100% | 15ms | 8560KB |

20 | AC | 100% | 25ms | 7872KB |

21 | AC | 100% | 44ms | 7856KB |

22 | AC | 100% | 39ms | 7600KB |

23 | AC | 100% | 41ms | 8096KB |

24 | AC | 100% | 3ms | 7888KB |

25 | AC | 100% | 39ms | 8112KB |

26 | AC | 100% | 44ms | 8560KB |

27 | AC | 100% | 18ms | 8464KB |

28 | AC | 100% | 45ms | 8544KB |

29 | AC | 100% | 28ms | 7904KB |

30 | AC | 100% | 38ms | 7600KB |

```
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1000000007;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int &e : a) cin >> e;
sort(a.begin(), a.end());
vector<int> dp(n + 1);
dp[1] = 1;
int sum = 1;
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1]) dp[i + 1] = dp[i];
else dp[i + 1] = sum;
sum = ((sum % MOD) + (dp[i + 1] % MOD)) % MOD;
}
cout << sum << '\n';
return 0;
}
```