VJ193259 I - A Boring Problem
2017-10-23
ACM
875
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
