day -1
老师说今早开家长会，我开始想今早模拟赛怎么打。
然后好像就是发了五道noip的题，最后又莫名其妙加了一个noip模拟赛。
day 0
本来说7：30起床，起晚了。
然后匆匆吃了点东西就开始打模拟赛。
与以往不同的是，本次比赛竟然使用的是 Lemon。
让我们自己在家评测。std、data之类的直接放我们这里。
然后 2735 就不停给我wx刷屏 T2 std。说这个代码可以骗分。
但是我没用。（）
因为我一直很排斥符号题目，所以看到 T1 愣了一下。
“什么？t1就这些乱七八糟的？”
仔细分析了一下，发现就是一个等差数列求积取模。
开干。其实就是 a(a+d)(a+2d)(a+3d)…(a+(n-1)d)，每个式子提一个d出来，最后来一个d的n次方。
其实一开始想去阶乘+前缀和，但是这个思路很快被该死的Gamma函数去掉了。为什么？Gamma我知道，分数阶乘，但是我不会。
然后只能继续将就了，就这样卡了十分钟。
然后？
哦！乘法逆元！
阶乘和乘法逆元提前预处理了一下，然后直接进去算式子。
然后就很快把代码写出来了。这个时候刚刚8点半，刚刚用了半小时。
调试一下：哦，我用了 unsigned long long，但是 printf("%ulld")，笑死我了，我是什么【】啊。
调试一下：哦，我模多了。
然后就一直在调bug…………………..
忘了说了，乘法逆元中途忘记怎么写了，手推了二十分钟。
调bug+推逆元=1个小时
最后半小时把代码写出来了，大样例炸了，发现是预处理预处理多了，果断直接预处理 1~mod-1。为什么？mod开始可以由逆元转化为其他的阶乘。然后快速幂炸了，原来是 b>>=1 写成 b<<=1 了。该死。
这个时候已经10点了，两个小时，把代码整理了一下，提交了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxt=1e7+10;
int t, p;
int times[maxt];
int exgcd[maxt];
int Pow(int a, int b){
int s=1;
for (; b; b>>=1, a=(ll)a*a%p)
if (b&1) s=(ll)s*a%p;
return s;
}
int main(){
freopen("story.in", "r", stdin);
freopen("story.out", "w", stdout);
scanf("%d %d", &t, &p);
*times=1;
for (int i=1; i<p; ++i) times[i]=(ll)times[i-1]*i%p;
exgcd[p-1]=Pow(times[p-1], p-2);
for (int i=p-1; i; --i) exgcd[i-1]=(ll)exgcd[i]*i%p;
while (t--){
int a, d, n;
scanf("%d %d %d", &a, &d, &n);
if (!d) printf("%d\n", Pow(a, n));
else{
a=(ll)a*exgcd[d]%p*times[d-1]%p;
printf("%d\n", (!a || a+n>p) ? 0 : (ll)times[a+n-1]*exgcd[a-1]%p*Pow(d, n)%p);
}
}
return 0;
}
第二题开题。题目一眼没用，没有被骗。发现了直接枚举字符串里所有 abcdcd 形状的种类输出即可。可惜没有写出 dp，还是太菜了。这个时候是11点。
第三题不会复杂背包，果断输出 Impossible。这个时候是11点25。
第四题线段树一点都不会，口胡了一个假思路，没写。这个时候是11点40。
摸鱼摸了20分钟，发现了VSCode扩展库里面的一些好东西。不得不说我从DEVC++换成VS是个明智的选择。因为我那个DEV是二次开发过的，RedPanda的一个劣质版本，往下滚轮都会出现那种 system("cls") 引起的间歇性刷新屏幕。
预估 [80,100]+0+[1,10]+0=[81,110]
最后是 100+0+9+0=109
总结：不能排斥符号堆砌的数学题。好多这种题都是唬人的，其实50行以内完事。背包、dp 还是大量刷大量刷，线段树不能不学了。
原文地址：http://www.cnblogs.com/kth-element/p/16906012.html
