徐州网站优化,宁化网站建设,湖北营销型网站建设价格,怎么申请百度网盘免费空间Description 一个长度为 \(n\) 的序列,初始都为 \(0\),你需要求出一个长度为 \(n-1\) 的排列 \(P\), 按照 \(1\) 到 \(n\) 的顺序,每次把 \(P_i\) 和 \(P_i1\) 染成 \(1\),一个排列的价值为所有的位置都变成 \(1\) 的操作次数,求所有排列的价值和题面 Solution 我们求出价值为 …Description 一个长度为 \(n\) 的序列,初始都为 \(0\),你需要求出一个长度为 \(n-1\) 的排列 \(P\), 按照 \(1\) 到 \(n\) 的顺序,每次把 \(P_i\) 和 \(P_i1\) 染成 \(1\),一个排列的价值为所有的位置都变成 \(1\) 的操作次数,求所有排列的价值和题面 Solution 我们求出价值为 \(\lceil\frac{n}{2}\rceil\) 到 \(n-1\) 的排列的方案数,然后分别算贡献就行了 操作最多 \(i\) 次的方案数是 \(f[i]\) 恰好 \(i\) 次的方案就是 \(f[i]-f[i-1]\) 而 \(f[i]C_{i-1}^{n-1-i}\) 具体含义:可以看作是每次可以选择 \(1,2\) ,求构成 \(n-2\) 的方案数,我们先默认都 \(1\),剩下就是选择 \(0,1\) 了,只要总共的 \(i-1\) 次操作中有 \(n-1-i\) 个选择了 \(1\),就一定可以达到目标了 #includebits/stdc.h
using namespace std;
templateclass Tvoid gi(T x){int f;char c;for(f1,cgetchar();c0||c9;cgetchar())if(c-)f-1;for(x0;c9c0;cgetchar())xx*10(c15);x*f;
}
const int N1e610,mod1e97;
int Fac[N],inv[N],n,f[N];
inline int C(int n,int m){return 1ll*Fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){freopen(pp.in,r,stdin);freopen(pp.out,w,stdout);cinn;int ans0,li(n1)/2;Fac[0]inv[0]inv[1]1;for(int i1;in;i)Fac[i]1ll*Fac[i-1]*i%mod;for(int i2;in;i)inv[i](mod-1ll*(mod/i)*inv[mod%i]%mod)%mod;for(int i2;in;i)inv[i]1ll*inv[i]*inv[i-1]%mod;for(int ili;in;i)f[i]1ll*C(i-1,n-1-i)*Fac[i]%mod*Fac[n-1-i]%mod;for(int in-1;ili;i--)f[i](f[i]-f[i-1]mod)%mod;for(int in-1;ili;i--)ans(ans1ll*i*f[i])%mod;coutansendl;return 0;
}转载于:https://www.cnblogs.com/Yuzao/p/8971726.html
