题目概述

定义 $0$ 维基础图形为点，$1$ 维基础图形为边，$2$ 维基础图形是正方形，$3$ 维基础图形是正方体，以此类推。问 $n$ 维基础图形由多少个 $m$ 维基础图形组成。

解题报告

感觉这题海星。应该不可能想象出 $4$ 维基础图形长什么样吧QAQ，所以找规律就只能在 $3$ 维之内找找的样子……

先定义个 $f_{m}(n)$ 表示答案，然后考虑下怎么递推，在三维里找找规律，可以想到是这样的：

$$ f_m(n)=2f_{m}(n-1)+f_{m-1}(n-1) $$

就是先把 $n-1$ 维基础图形复制一遍，再把这两个 $n-1$ 维基础图形拼起来，此时降维了，所以需要的是 $m-1$ 维基础图形拼成的 $n-1$ 维基础图形。

但是这样是 $O(nm)$ 的，需要化简，所以从 $m=0$ 开始推下式子：

$$ f_{0}(n)=2^n\\ \begin{aligned} f_{1}(n)&=2f_1(n-1)+f_0(n-1)=2f_1(n-1)+2^{n-1}\\ &=2[2f_1(n-2)+f_0(n-2)]+2^{n-1}\\ &=4f_1(n-2)+2^{n-1}+2^{n-1}\\ &=\cdots=n2^{n-1} \end{aligned}\\ \begin{aligned} f_{2}(n)&=2f_2(n-1)+f_1(n-1)=2f_2(n-1)+(n-1)2^{n-2}\\ &=2[2f_2(n-2)+f_1(n-2)]+(n-1)2^{n-2}\\ &=4f_2(n-2)+(n-2)2^{n-2}+(n-1)2^{n-2}\\ &=\cdots={n(n-1)\over2}2^{n-2} \end{aligned}\\ \cdots $$

很容易发现后面是 $2^{n-m}​$ ，前面的系数也很熟悉，是 $n\choose m$（因为 $\sum_{i=m-1}^{n-1}{i\choose m-1}={n\choose m}​$ ）。

那么答案就是 $f_{m}(n)={n\choose m}2^{n-m}​$ 。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,MOD=998244353;

int te,n,m,fac[maxn+5],INV[maxn+5],pw[maxn+5];

inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=(pw[i-1]<<1)%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(maxn),scanf("%d",&te);te;te--)
        scanf("%d%d",&n,&m),printf("%lld\n",(LL)C(n,m)*pw[n-m]%MOD);return 0;
}