ZigZagK的博客
[DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解
2019年2月28日 22:00
LOJ
查看标签

题目概述

定义 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!