結果
問題 | No.118 門松列(2) |
ユーザー |
![]() |
提出日時 | 2021-11-08 16:22:39 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 10 ms / 5,000 ms |
コード長 | 634 bytes |
コンパイル時間 | 2,078 ms |
コンパイル使用メモリ | 29,312 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 11:05:43 |
合計ジャッジ時間 | 2,090 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include<stdio.h> int main() { int n; scanf("%d", &n); int i; int a[100005]; for (i = 0; i < n; i++) scanf("%d", &a[i]); long long int p = 1000000007; long long int cnt[102]; for (i = 0; i < 102; i++) cnt[i] = 0; for (i = 0; i < n; i++) cnt[a[i]]++; long long int dp[3][102]; for (i = 0; i < 102; i++) dp[0][i] = dp[1][i] = dp[2][i] = 0; dp[0][0] = dp[1][0] = dp[2][0] = 0; for (i = 1; i < 102; i++) { dp[2][i] = (cnt[i] * dp[1][i - 1] % p + dp[2][i - 1]) % p; dp[1][i] = (cnt[i] * dp[0][i - 1] % p + dp[1][i - 1]) % p; dp[0][i] = (cnt[i] + dp[0][i - 1]) % p; } printf("%lld\n", dp[2][101]); return 0; }