[CF932E] Team Work

一时失言乱红尘 2021-09-30 12:06 220阅读 0赞

## 题目链接 ##

Codeforces：[https://codeforces.com/problemset/problem/932/E][https_codeforces.com_problemset_problem_932_E]

## Solution ##

直接把幂转成斯特林数然后暴力就好了。  
\\\[ \\begin\{align\}ans=&\\sum\_\{i=1\}^\{n\}\\binom\{n\}\{i\}i^x\\\\=&\\sum\_\{i=1\}^\{n\}\\binom\{n\}\{i\}\\sum\_\{j=1\}^\{k\}s\_2(k,j)\\binom\{i\}\{j\}j!\\\\=&\\sum\_\{j=1\}^\{k\}s\_2(k,j)\\frac\{n!\}\{(n-k)!\}2^\{n-j\}\\end\{align\} \\\]  
复杂度\\(O(k^2)\\)。

#include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define ll long long #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 5e3+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int n,k,s[maxn][maxn],ans; int qpow(int a,int x) { int res=1; for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod; return res; } int main() { read(n),read(k);s[0][0]=1; for(int i=1;i<=k;i++) for(int j=1;j<=i;j++) s[i][j]=(1ll*j*s[i-1][j]+s[i-1][j-1])%mod; for(int i=1;i<=k&&i<=n;i++) { int res=1; for(int j=n;j>n-i;j--) res=1ll*res*j%mod; res=1ll*res*qpow(2,n-i)%mod; res=1ll*res*s[k][i]%mod; ans=(ans+res)%mod; } write(ans); return 0; }

转载于:https://www.cnblogs.com/hbyer/p/10876493.html

[https_codeforces.com_problemset_problem_932_E]: https://codeforces.com/problemset/problem/932/E

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 74 阅读

相关【构造】CF1761 E

[Problem - 1761E - Codeforces][] 题意： ![0622cda9a5a44fcfbb3df51c5babd8bc.png][] 思路：

缺乏、安全感/ 2024年03月23日 22:53/ 0 赞/ 83 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 63 阅读

相关【DP】CF598E

[Problem - E - Codeforces][] ![ea06301014c348d39e3a5f448de96951.png][] Code： incl

深碍√TFBOYSˉ_/ 2024年03月22日 22:01/ 0 赞/ 86 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 19 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 121 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 214 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 214 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 270 阅读

相关 [CF932E] Team Work

题目链接 Codeforces：[https://codeforces.com/problemset/problem/932/E][https_codeforces.co

一时失言乱红尘/ 2021年09月30日 12:06/ 0 赞/ 221 阅读