pekempey's blog

998244853

CF 581 Div2. E. Natasha, Sasha and the Prefix Sums

https://codeforces.com/contest/1204/problem/E

I just wanted to draw figures.

f:id:pekempey:20190821032408p:plain:w400

f:id:pekempey:20190821032416p:plain:w400

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

constexpr int MOD = 998244853;

void add(int &x, int y) { x += y; x -= (x >= MOD) * MOD; }

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  vector<int> c(n + m + 1);
  c[0] = 1;
  rep(_, n + m) repr(i, n + m) add(c[i + 1], c[i]);
  int ans = 0;
  for (int i = 1; i <= n; i++) add(ans, n - m >= i ? c[n] : c[m + i]);
  cout << ans << endl;
}
\documentclass[dvipdfmx,margin=2mm]{standalone}
\usepackage{tikz}
\usetikzlibrary{decorations.markings}
\begin{document}

% https://ipfs-sec.stackexchange.cloudflare-ipfs.com/tex/A/question/39278.html
\tikzset{->-/.style={decoration={
  markings,
  mark=at position #1 with {\arrow{latex}}},postaction={decorate}}}

\begin{tikzpicture}
  \node [anchor=west] at (0,5) {$n=4,m=3$};

  \draw[thick,-latex] (0,0) -- (7,0);
  \foreach \i in {0,1,2,3} \draw[dashed] (\i,-\i) -- (\i+4,-\i+4);
  \foreach \i in {0,1,2,3,4} \draw[dashed] (\i,\i) -- (\i+3,\i-3);
  \draw [thick] (0,2) -- (7,2);
  \node at (8,2) {$k=2$};
  \foreach \a/\b/\c/\d in {0/0/1/1, 1/1/2/2, 2/2/3/3, 3/3/4/2, 4/2/5/1, 5/1/6/2, 6/2/7/1}
    \draw[thick,->-=.5] (\a,\b) -- (\c,\d);
  \node[inner sep=0,minimum size=1mm,fill=black,circle] at (7,1) {};
\end{tikzpicture}

\end{document}
\documentclass[dvipdfmx,margin=2mm]{standalone}
\usepackage{tikz}
\usetikzlibrary{decorations.markings}
\begin{document}

% https://ipfs-sec.stackexchange.cloudflare-ipfs.com/tex/A/question/39278.html
\tikzset{->-/.style={decoration={
  markings,
  mark=at position #1 with {\arrow{latex}}},postaction={decorate}}}

\begin{tikzpicture}
  \node [anchor=west] at (0,5) {$n=4,m=3$};

  \draw[thick,-latex] (0,0) -- (7,0);
  \foreach \i in {0,1,2} \draw[dashed] (\i,-\i) -- (\i+5,-\i+5);
  \foreach \i in {0,1,2,3,4,5} \draw[dashed] (\i,\i) -- (\i+2,\i-2);
  \draw [thick] (0,2) -- (7,2);
  \foreach \a/\b/\c/\d in {0/0/1/1, 1/1/2/2, 2/2/3/1, 3/1/4/2, 4/2/5/3, 5/3/6/2, 6/2/7/3}
    \draw[thick,->-=.5] (\a,\b) -- (\c,\d);
  \draw[thick,-latex] (7,1) to[bend right] node[anchor=west] {} (7,3);
  \node[inner sep=0,minimum size=1mm,fill=black,circle] at (7,1) {};
  \node[inner sep=0,minimum size=1mm,fill=black,circle] at (7,3) {};
\end{tikzpicture}

\end{document}