yukicoder contest 369 H

解き方

結論をまず述べると、これは次のように求めることができる。

この方法の正当性を証明するため、下記の主張を帰納的に証明する。

$ \sum_{l = 1}^{n!} (x_{l}+1)^{j} = \sum_{l=1}^{n!} \sum_{k=0}^{j} \left( {}_{j} \mathrm{C}_{k} \times x_{l}^{k} \right) = \sum_{k = 0}^{j} \left( {}_{j} \mathrm{C}_{k} \times \left( \sum_{l=1}^{n!} x_{l}^{k} \right) \right) = \sum_{k=0}^{j} {}_{j} \mathrm{C}_{k} \times \mathrm{dp}(n, k)

$ n\times\mathrm{dp}(n,j) + \sum_{k=0}^{j} {}_{j} \mathrm{C}_{k} \times \mathrm{dp}(n, k) = \mathrm{dp}(n+1, j)

解答例

下は上記の方法で解いたときの提出結果である。また、上記の提出の際に提出したソースコードをその下に転記する。

code: C

int main () {

int n = 0;

int res = 0;

long long mod_num = 998244353LL;

long long ans1 = 1LL;

long long ans2 = 1LL;

long long ans3 = 1LL;

long long fact = 1LL;

res = scanf("%d", &n);

for (int i = 2; i <= n; i++) {

long long tmp1 = ans1+fact;

long long tmp2 = ans2+2LL*ans1+fact;

long long tmp3 = ans3+3LL*ans2+3LL*ans1+fact;

ans1 *= (long long) (i-1);

ans2 *= (long long) (i-1);

ans3 *= (long long) (i-1);

ans1 += tmp1;

ans2 += tmp2;

ans3 += tmp3;

ans1 %= mod_num;

ans2 %= mod_num;

ans3 %= mod_num;

fact *= (long long)i;

fact %= mod_num;

}

printf("%lld\n", ans3%mod_num);

return 0;

}

私の提出一覧

table: submissions_yukicoder_contest_369_H

提出のURL 提出時刻 結果 備考

感想

解けないのにF問題やG問題について悩んで時間を使ってしまったので、この問題を解くのに使った時間は20分間もなかったかな。

時間内に解けそうだったかな（結局はミスがあったから時間内には解けなかったけれど）

しかし、解説をみたら、やはり全然違うことを書いてあるように思えて、解けたと言って良いかは微妙（実はまだ解説を理解できていない）

時間内に解けなかったのは、ループ回数の階乗を表すつもりの変数を、ループ内で全く更新していなくて階乗になっていなかったから。

終了ギリギリに気づいて直して提出しようとしたけれど、ギリギリだったので焦りすぎて、剰余を取り忘れたまま提出してしまった。

提出とほぼ同時に気がついて…