How to type a map where the type of the value depends on the type of the key?

The TypeScript typings for Map only support Map<K, V>, where K is the key type, V is the value type, and there is no further correlation between them. So if you just use Map as-is, you cannot get the TypeScript compiler to enforce extra constraints.

From my reading of your question, I understand your constraint to be that the key should be a (possibly abstract) constructor type, and that for each key, the value should be a (necessarily concrete) constructor of a compatible type. And since your example code only uses the set() method, the minimum typings to get your example code to behave as desired look like this:

interface MySpecialMap {
  set<T extends object>(
    k: abstract new (...args: any) => T, 
    v: new (...args: any) => T
  ): this;
}
interface MySpecialMapConstructor {
  new(): MySpecialMap;
}
const MySpecialMap: MySpecialMapConstructor = Map;

Here I've defined the MySpecialMap constructor to be just the Map constructor at runtime, but I've given it the type MySpecialMapConstructor, which constructs instances of MySpecialMap. The MySpecialMap interface has only one method, set(), which is generic in the type T of the base class instances. The k parameter is a possibly abstract constructor of type T instances, while the v parameter is a necessarily concrete constructor of type T instances.

Let's demonstrate that it works as desired:

abstract class BaseA { a() { } }
class ConcreteA1 extends BaseA { a1() { } }
class ConcreteA2 extends BaseA { a2() { } }
abstract class BaseB { b() { } }
class ConcreteB extends BaseB { b1() { } }

const map = new MySpecialMap();
map.set(BaseA, ConcreteA1); // ok
map.set(BaseA, ConcreteA2); // ok
map.set(BaseB, ConcreteB);  // ok
map.set(BaseA, ConcreteB); // error
// Property 'a' is missing in type 'ConcreteB' but required in type 'BaseA'
map.set(BaseA, BaseA); // error
// Cannot assign an abstract constructor type to a non-abstract constructor type.

Looks good!

After this you presumably want to add similar typings for get() or any other methods you need. Or you might want to change the call signature for set() to specify zero-arg constructors or any other constraint you want to enforce. But hopefully this should get you started.

Playground link to code

TypeScript is a Structural Type System. A structural type system means that when comparing types, TypeScript only takes into account the members on the type. This is in contrast to nominal type systems, where you could create two types but could not assign them to each other. (Read more here)

In order to go passed that you can uniquify your base class (e.g. adding a private member #type). Using that, you can create a new type that would only allow certain maps to exist. Here's an example:

abstract class BaseA {
    #type = BaseA.name;
}
class ConcreteA extends BaseA {
}
abstract class BaseB {}
class ConcreteB extends BaseB {
}

type MyMap<T, S> = S extends T ? Map<T, S> : never; 
const map1: MyMap<BaseA, ConcreteA> = new Map();
//    ^?
const map2: MyMap<BaseA, ConcreteB> = new Map();
//    ^?

Link to the playground