二项展开
1

2017

1

Problem 给定数字串 S,求如下表达式的值: Solution 用前缀和转化该式。令 , 则 . 原式转化为: 二项展开,得: 将内外求和对调,使得可以预处理前缀和的和的p次方。式子化为: 预处理 , 复杂度 O(N*K). 对 , 处理每个答案,复杂度也是 O(N*K). 坑点: 每个case末尾输出空格PE. 最后不输出换行会WA... 于是我从PE改到了WA... Code #include <cstdio> #include <cstring> typedef long long LL; const LL MOD=1e9+7; const int MAXN=5e4+10; char S[MAXN]; LL pre[MAXN]; LL spre[MAXN][110]; LL ppre[MAXN][110]; LL C[110][110]; void init() { C[0][0]=1; for (int i=1;i<=100;++i) { C[0