Le tableau de pointeurs fonctionne plutôt bien pour un tableau comme ça, mais du coup, je dirais que ta structure de données est foireuse.

Pour le cas où M_N ne dépend pas de N (c'est-à-dire le cas d'un M constant), on peut s'arranger même si on ne le connaît pas à la compilation (cf. tableaux à taille variable du standard C99).