突然发现，做TC的500就像终场前的绝杀， 虽然难，但是还是有可能的，但是1000pt，尼玛几乎就是35秒13分啊！
500pt ：
题意：给你一个字符串由I O ？ 三种字符构成，现在让你将? 变成 I 或者 O，使得原序列存在至少一种这样子的情况：两个I关于一个O对称。
花了十几秒时间想了下直接算行不行，发现这是NP啊。。果断反过来想，YY良久，还是没结果，，看了题解后陷入了深深的反思，其实只要我尝试着画一画非法的字符串长什么样子，肯定能独立搞出来的，还是没经验 啊。。
解法：假设就给你若干个“?”，只要你在纸上写写非法的字符串长什么样子，这个问题其实就解决了。
再一次陷入沉思+反思。。。。。
int p[2550];
int IOIString :: countIOIs(vector <string> mask){
string s = "";
for(int i = 0; i < mask.size(); i++) {
for(int j = 0; j < mask[i].length(); j++){
s += mask[i][j];
}
}
int n = s.size();
p[0] = 0;
for(int i = 0; i < n; i++) {
p[i+1] = p[i];
if(s[i] == 'I') p[i+1] ++;
}
int sum = 0;
if(!p[n]) sum++;
for(int i = 0; i < n; i++) if(!p[i]){
if(s[i] == 'O') continue;
else if(p[n]-p[i+1]==0)sum ++;
for(int d = 1; d < n; d+=2) {
for(int j = i+d; j < n; j+=d) {
if(p[j-1 + 1] - p[j-d + 1]) break;
if(s[j] == 'O') break;
if(p[n] - p[j+1] == 0)sum ++;
}
}
}
int cnt = 1;
for(int i = 0; i < n; i++) {
if(s[i] == '?') {
cnt*=2;
cnt%=mod;
}
}
return (cnt - sum + mod) % mod;
}
// BEGIN CUT HERE
int main() {
IOIString ___test;
___test.run_test(-1);
}
// END CUT HERE
1000pt：
题意：问你由0~9构成长度为n的非递减序列而且能整除m的序列的个数。(n<=10^18 , m<=500).
仰慕某些能一眼看出来性质的神牛，反正我是没看出来，看出那个关键的性质后，问题就是一个简单的DP了。
关键性质：这样一个非递减的序列肯定能由小于等于9个形如(1111...111)的数构成，而且(1111.....111)(n个1)必须要存在（保证n位）。
然后考虑到数的种类太多，而且对于一个数我们只需要知道这个数对余数的贡献就好了。所以，我们重新分类，利用所有的数对m取余的结果，这样子就相当于将所有的数分成了m个剩余类，然后我们从余数为0的类开始取dp[i][j][k]表示前i类，取了j个数，余数为k的总方案数。
WA两发，预处理的时候没有考虑清楚整除循环节的情况
TLE一发：没有预处理逆元
总结：我真弱！
/* **********************************************
Author : wuyiqi
Created Time: 2013-8-11 10:39:19
File Name : final.cpp
*********************************************** */
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
typedef __int64 lld;
const int mod = 1000000007;
//typedef long long lld;
class IncreasingNumber {
public:
int countNumbers(long long digits, int divisor) ;
};
lld cnt[510];
int pos[510];
int last;
void init(lld n,int m){
memset(cnt,0,sizeof(cnt));
if(m==1) {
last = 0;
cnt[0] = n-1;
return ;
}
int i;
int pre = 0 , sum = 0;
memset(pos,-1,sizeof(pos));
int rep = -1;
int rec[550];
for(i = 1; i < n; i++) {
sum = sum * 10 + 1;
sum %= m;
rec[i] = sum;
if(pos[sum] != -1) {
rep = i - pos[sum];
break;
}
pos[sum] = i;
cnt[sum] ++;
}
if(rep == -1) {
last = (sum*10+1) % m;
}
else {
n = n - (i-1) ;
lld ti = n / rep;
lld left = n % rep;
for(int j = i-1; j >= i-rep; j--) {
cnt[rec[j]] += cnt[rec[j]] * ti;
}
for(int j = i-rep; j <= i-rep+left-2; j++) {
cnt[rec[j]] ++;
}
if(left == 0) {
cnt[rec[i-1]] --;
last = rec[i-1];
}else
last = rec[i-rep+left-1];
}
}
lld Pow(lld x,int y) {
lld ans = 1;
while(y){
if(y&1) ans=ans*x%mod;
y >>= 1; x = x * x % mod;
}
return ans;
}
lld fac[10];
lld CC(lld n,lld k) {
if(k > n) return 0;
lld ans = 1;
for(int i = 1; i <= k; i++) {
ans = (n-i+1)%mod * ans % mod % mod;
}
ans = ans * fac[k] % mod;
return ans;
}
lld dp[510][10][510];// dp[i][j][k] 前i类（剩余类），选了j个，余数为k
inline void Add(lld &x,lld y) {
x += y;
if(x >= mod) x -= mod;
}
int pre[510][10][510];
lld gao(int m) {
for(int k = 0; k < m; k++) {
for(int go = 0; go <= 8; go++) {
for(int i = 0; i < m; i++) {
pre[k][go][i] = (k+go*i)%m;
}
}
}
fac[0] = 1;
for(int i=1;i<10;i++) fac[i] = fac[i-1]*i;
for(int i=1;i<10;i++) fac[i] = Pow(fac[i],mod-2);
memset(dp,0,sizeof(dp));
dp[0][0][0] = 1;
for(int i = 0; i < m; i++) {
for(int j = 0; j <= 8; j++) {
for(int k = 0; k < m; k++) if(dp[i][j][k]){
Add(dp[i+1][j][k],dp[i][j][k]);
for(int go = 1; go+j <= 8; go++) if(cnt[i]){
lld tmp = dp[i][j][k] * CC(cnt[i]+go-1,go) % mod;
Add(dp[i+1][go+j][pre[k][go][i]] , tmp);
}
}
}
}
lld ans = 0;
for(int i = 1; i <= 9; i++) {
for(int j = 0; j + i <= 9; j++){
ans += dp[m][j][(m-i*last%m)%m];
ans %= mod;
}
}
return ans;
}
int IncreasingNumber::countNumbers(lld n,int M) {
init(n,M);
return (int)gao(M);
}
// BEGIN CUT HERE
int main() {
IncreasingNumber ___test;
___test.run_test(-1);
}
// END CUT HERE
总结：这场的500和1000pt都是属于观察题（其实什么题不是这样子的呢QAQ），发现了关键性质就能AC，而且性质也并不是那么隐晦，500分的关键是要动手去写，很多人都能想到第一步，要反着计算，然后剪掉，但是在反着算那些非法串的数量的时候却忘了去分析非法串的性质了，如上所述，只需要写几个非法串观察一下性质，结果就出来了。
学会举几个例子，在纸上画一画，这一点真的很重要，分析的多了，能解决很多问题。
1000pt，典型的思维定势了。虽然也想到了最终的解题方法肯定跟10^18扯不上关系，但是没有抓住这种非递减序列的特殊性，可以分拆成有限的几个1111形式的数字。然后再利用余数很小这一特定，划分剩余类，将10^18的数就分成了500类，最后再转换成普通的dp来取就好 了。
继续吧。