T1 论逼格
最近，王第一决定想办法提升自己的逼格。经过数日的研究，他发现：回文数字是非常有逼格的。为了让自己成为一个更有逼格的人，他想要知道：\[S_n = \sum\limits_{i = 1}^{n}i \cdot s_i \cdot [i \% 2]\]
其中，\(s_i\)是长度为\(i\)的回文数个数（不含前导\(0\)），最后面的括号是布尔表达式。
答案对\(233333\)取模
\(T\)组询问，\(T \leq 10^5 ,n \leq 10 ^ 9\)。
推式子就好了，最后是个等差乘等比。考场降智最为致命……
考虑长为\(i\)时\(s_i\)
剩下的就是正常等差乘等比的求和公式推导:错位相减
推导完了，这样就可以\(log\)计算了。
另外，\(233333\)不是质数，无法用费马小定理求逆元。
inline int sov(int n)
{
register int len = qpow(10, n - 1);
register int len1 = (long long)len * 10 % MOD;
register int res1 = (long long)(2 * n - 1) * len1 % MOD;
register int res2 = 20ll * (1 - len) % MOD * RMOD % MOD;
return (res1 + res2 - 1 + MOD) % MOD;
}
int main()
{
poread(T);
while (T--)
{
poread(n);
printf("%d\n", sov((n + 1) / 2));
}
}T2购物
\(Jackpei\) 喜欢购物，他尤其喜欢那种横扫一片商店的快感。最近，他打算对南门口的商店实行他疯狂的购物计划。南门口的商业区中最繁华的就是黄兴路步行街了。这条街上有\(n\)个商店，\(Jackpei\) 打算进攻\(m\)次，每次扫荡第\(L_i , R_i\)个商店，\(Jackpei\)会把他经过的每个商店扫荡一空（换句话说，就是一个商店不会被算两次），因为连续地扫一片商店是很爽的，所以 \(Jackpei\) 把一次扫荡的\(happy\)值定义为所有连续的一段没被扫空的商店\(happy\)值之和的平方的和，已被扫空的不再计算。
求扫荡的顺序以得到最大\(happy\)之和。
\(n \leq 5000 , m \leq 10^6\)
贪心策略：每次取当前的贡献最大的最大可行方案。因为之后该方案的贡献只减不增。
对每个\(i\)维护他能连续到的最远右端点即可。
int main()
{
poread(n);
poread(m);
for (register int i = 1; i <= n; ++i)
poread(a[i]), a[i] = a[i - 1] + a[i];
for (register int i = 1, x, y; i <= m; ++i)
poread(x), poread(y), poi[x] = max(poi[x], y);
long long ans = 0;
for (register int i = 1; i <= n; i)
{
register int sum = 0, st = 0, ed = 0;
for (register int j = 1; j <= n; ++j)
if (a[poi[j]] - a[j - 1] > sum && poi[j])
sum = a[poi[j]] - a[j - 1], st = j;
ed = poi[st];
if (!sum)
{
printf("%lld", ans);
return 0;
}
ans += (long long)sum * sum;
for (register int j = 1; j <= st; ++j)
{
if (poi[j] >= st)
poi[j] = st - 1;
}
for (register int j = st; j <= ed; ++j)
{
if (poi[j] > poi[ed + 1])
poi[ed + 1] = poi[j];
poi[j] = 0;
}
}
}开long long... 自己把自己hack了
T3 宗教仪式
所以，nofind 决定：对于 中的某个位置 ，设 ，若：
（最外层中括号为布尔表达式）则认为 在 处出现了一次。
nofind 想知道， 在 中一共出现了多少次？
本来一上午加一中午用哈希 + 二分 把这题卡过去了
结果jackpei疯狂制造hack数据把我ri了。。。
就先放哈希 + 二分吧。学完正解后缀数组再来。
const int BS = 300010;
static char buf[BS];
short k;
int M = 97;
int T1, T2;
int p[200001];
int s1[200001], s2[100001];
inline int find(const int &x, const int &y)
{
register int l = 0, r = min(T1 - x, T2 - y), res = 0, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (s1[x + mid] - s1[x] * p[mid] == s2[y + mid] - s2[y] * p[mid])
res = mid, l = mid + 1;
else
r = mid - 1;
}
return res;
}
inline bool check(int x, int y)
{
register int tmp;
for (register short i = 1; i <= k; ++i)
{
tmp = find(x - 1, y - 1);
x += tmp + 1, y += tmp + 1;
if (y > T2)
return true;
// cerr << x << " " << y << '\n';
}
tmp = find(x - 1, y - 1);
x += tmp, y += tmp;
return y > T2;
}
signed main()
{
register char c = 0;
register int *t1 = s1, *t2 = s2;
register char *st, *ed;
scanf("%s", buf + 1);
T1 = strlen(buf + 1);
st = buf + 1;
for (register int *t1 = s1 + 1; t1 <= s1 + T1; ++t1, ++st)
{
*t1 = *(t1 - 1) * M + *st;
}
scanf("%s", buf + 1);
T2 = strlen(buf + 1);
st = buf + 1;
for (register int *t2 = s2 + 1; t2 <= s2 + T2; ++t2, ++st)
{
*t2 = *(t2 - 1) * M + *st;
}
scanf("%d", &k);
p[0] = 1;
for (register unsigned i = 1; i <= T1; ++i)
{
p[i] = p[i - 1] * M;
}
register int t = T1 - T2 + 1;
register int ans = 0;
for (register int i = 1; i <= t; ++i)
{
ans += check(i, 1);
}
printf("%d", ans);
}