桂林尚品网络做的网站好不好,一个公司可以做多少网站,常熟有哪些网站建设公司,重庆景点排行榜题解
这是一道纯粹的数学求导题目。 首先我们先写出要求的公式。 ans∑r1nCnrrkans \sum_{r1}^{n} C_n^{r}r^kans∑r1nCnrrk 乍一看#xff0c;雾草好吓人#xff0c;但是学过高等数学且稍有常识的人#xff08;不是我#xff09;可以看出#xff0c;这个可以由某个…题解
这是一道纯粹的数学求导题目。 首先我们先写出要求的公式。 ans∑r1nCnrrkans \sum_{r1}^{n} C_n^{r}r^kans∑r1nCnrrk 乍一看雾草好吓人但是学过高等数学且稍有常识的人不是我可以看出这个可以由某个式子不断乘x并求导得出来。 没错稍有常识的人又可以看出来了这个式子就是(1x)n(1x)^n(1x)n (1x)n∑r0nCnrxr(1x)^n \sum_{r0}^{n}C_n^{r}x^r(1x)n∑r0nCnrxr 我们定义 f0ddx(1x)nn(1x)n−1f_0 \frac{d}{dx}(1x)^n n(1x)^{n-1}f0dxd(1x)nn(1x)n−1 同时f0(x)∑r1nCnrrxr−1f_0(x) \sum_{r1}^{n} C_n^{r}rx^{r-1}f0(x)∑r1nCnrrxr−1 定义ft(x)ddx(xft−1(x))f_t(x) \frac{d}{dx}(xf_{t-1}(x))ft(x)dxd(xft−1(x)) 这样的话fk−1(x)∑r1nCnrrkf_{k-1}(x) \sum_{r1}^{n} C_n^{r}r^kfk−1(x)∑r1nCnrrk 那么我们要求的答案ansfk−1(0)(1)ans f_{k-1}^{(0)}(1)ansfk−1(0)(1) 我们知道ft(x)ddx(xft−1(x))ft−1(x)xft−1(1)(x)f_t(x) \frac{d}{dx}(xf_{t-1}(x))f_{t-1}(x)xf_{t-1}^{(1)}(x)ft(x)dxd(xft−1(x))ft−1(x)xft−1(1)(x) 通过这个操作ft(p)(1)(p1)ft−1(p)(1)ft−1(p1)(1)f_t^{(p)}(1) (p1)f_{t-1}^{(p)}(1)f_{t-1}^{(p1)}(1)ft(p)(1)(p1)ft−1(p)(1)ft−1(p1)(1) 没错这就是我们的递推公式 定义dp[i][j]fi(j)(1)dp[i][j] f_{i}^{(j)}(1)dp[i][j]fi(j)(1) dp[i][j](p1)∗dp[t−1][p]dp[t−1][p1]dp[i][j] (p1)*dp[t-1][p]dp[t-1][p1]dp[i][j](p1)∗dp[t−1][p]dp[t−1][p1] 由于我们只需要ansdp[k−1][0]ansdp[k-1][0]ansdp[k−1][0]那么就只需要dp[k−2][0...1]dp[k-2][0...1]dp[k−2][0...1],…,只需要dp[0][0...k−1]dp[0][0...k-1]dp[0][0...k−1] 状态数O(K2)O(K^2)O(K2) 代码
#include cstdio
#include iostream
#include algorithm
using namespace std;
typedef long long ll;
ll N,k;
const ll mod 1e97;
const int maxn 5007;
ll dp[maxn][maxn],sum[maxn];
ll mod_pow(ll x,ll n){ll ans 1;while(n){if(n1)ans ans * x % mod;x x*x%mod;n 1;}return ans;
}
int main(){cinNk;if(N 1){return 0*printf(1\n);}ll pre N;for(int t 0;t min(N,5005ll);t){dp[0][t] pre*mod_pow(2,N-1-t)%mod;pre pre*(N-1-t)%mod;}for(int i 1;i k;i){for(int j 0;j k;j){dp[i][j] ((j1)*dp[i-1][j] dp[i-1][j1])%mod;}}printf(%lld\n,dp[k-1][0]);return 0;
}
