ERROR: cuvid requested, but not all dependencies are satisfied: cuda/ffnvcodec

The NVIDIA headers were moved out of the FFmpeg codebase to a standalone repository in commit 27cbbbb. From the commit message:

External headers are no longer welcome in the ffmpeg codebase because they increase the maintenance burden. However, in the NVidia case the vanilla headers need some modifications to be usable in ffmpeg therefore we still provide them, but in a separate repository.

Also, from FFmpeg Wiki: HWAccelIntro:

FFmpeg now uses its own slightly modified runtime-loader for nvidias CUDA/nvenc/nvdec related libraries. If you get an error from configure complaining about missing ffnvcodec, this is what you need.

It has a working Makefile with an install target:

make install PREFIX=/usr

FFmpeg will look for its pkg-config file, called ffnvcodec.pc. Make sure it is in your PKG_CONFIG_PATH.

To compile the FFmpeg NVIDIA headers ("ffnvcodec"):

git clone https://git.videolan.org/git/ffmpeg/nv-codec-headers.git
cd nv-codec-headers
make
sudo make install

Now compile ffmpeg as usual. The headers should be autodetected. If not then declare the PKG_CONFIG_PATH pointing to the path where ffnvcodec.pc is located when running configure for FFmpeg. For example:

PKG_CONFIG_PATH="/path/to/lib/pkgconfig" ./configure

I encountered a similar error but it turns out, it was caused by missing tool package config. On Ubuntu 16.04 you can run

apt-get install pkgconf

and check whether the missing package is really missed or not:

pkgconf --list-all | grep package-name