A faster approach
It's possible to solve this in $O(\binom{n}{t} \cdot n)$ operations, i.e., at most $O(n^{t+1})$ operations. This is faster than the algorithm you describe in your question by about a factor of $t!$, but probably still not fast enough to be feasible for your parameters.
The idea is to enumerate all possible subsets of $t$ elements. We'll try all possible choices for $S$, the set of elements that occur in positions $1,2,\dots,t$ (without regard to what order they appear in). There are $\binom{n}{t}$ such choices for $S$.
For each choice of $S$, we separately (i) count the number of ways to order the elements of $S$ so that the first $t$ elements satisfy the first condition, and (ii) count the number of ways to order the elements of $\{1,2,\dots,n\}\setminus S$ so that the last $n-t$ elements satisfy the second condition. Then, we multiply these two counts.
Each of those counts can be computed efficiently. For instance, to compute count (i), we compute
$$g(t) \times (g(t-1)-1) \times (g(t-2)-2) \times \dots \times (g(1)-(t-1)),$$
where $g(i) = |S \cap \{1,2,\dots,f(i)\}|$ counts the number of elements of $S$ that could potentially be used at position $i$ without violating the first condition (i.e., the number of elements of $S$ that are $\le f(i)$). Similarly, to compute count (ii), we compute
$$h(t+1) \times (h(t+2)-1) \times (h(t+3)-2) \times \dots \times (h(n)-(n-t+1)),$$
where $h(i) = |\overline{S} \cap \{f(i),\dots,n\}|$.
These two counts can be computed using $O(n)$ operations, leading to the claimed running time.
A further optimization
You can further optimize this, by splitting $S$ into two parts. Decompose $S$ into
$$S = S_1 \cup S_2,$$
where $S_1 \cap S_2 = \emptyset$, by defining
$$\begin{align*}
S_1 &= S \cap \{f(t+1),f(t+1)+1,\dots,n-1,n\}\\
S_2 &= S \cap \{1,2,3,\dots,f(t+1)-1\}.
\end{align*}$$
Now notice that to count (ii), we don't actually need to know both $S_1$ and $S_2$: it's enough to know $|S_1|$ and $S_2$: the exact elements in $S_1$ don't change the count (by a relabelling argument), since they're all $\ge f(j)$ for all $j>t$.
Furthermore, since $|S|=t$ and $|S|=|S_1|+|S_2|$, it suffices to know $S_2$. Once we know $S_2$, we can compute $|S_1|=t-|S_2|$ and then compute count (ii).
Similarly, once we know $S_2$, we can also compute count (i).
So, we're going to enumerate all possible values for $S_2$, i.e., all subsets of $\{1,2,3,\dots,f(t+1)-1\}$ of size $\le t$. There are
$$Q = \binom{f(t+1)-1}{t} + \dots + \binom{f(t+1)-1}{1} + \binom{f(t+1)-1}{0}$$
possible choices for $S_2$. Then we obtain an algorithm whose running time is $O(Q \cdot n)$. The exact value of $Q$ depends on $f(t+1)$, but we have $Q = O(f(t+1)^t)$.
In this way we obtain an algorithm whose running time is $O(f(t+1)^t \cdot n)$. For many choices of $f$, this will be even faster than the basic approach sketched at the beginning of this answer.
Also, it's easy to see that we must have $f(t+1) \ge n-t+1$ (otherwise the count is 0). It follows that there is an algorithm whose worst-case running time is $O((n-t)^t \cdot n)$, regardless of $f$.
