~~bzoj早就老了~~现在最受欢迎的OJ当然是你谷了，一些比较经典的题目还是很不错的。
LINK：想了好几个月的dp 翻硬币 我想到一个状态 f[i][j]表示翻了i次且当前局面为j的方案数最后输出f[n][目标方案即可]。
但是这里面存在着一些问题 好像这个转移都是一个组合数级别的所以不可能转移出来的 。突然有一个想法设f[i][j]表示经过i次翻转有j个位置是合法的方案数这样就可以转移了。
n^2递推组合数即可。
//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 1000000000 #define ll long long #define db double #define mod 1000000007 using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } const ll MAXN=110; ll n,m,k,cnt; ll c[MAXN][MAXN]; ll f[MAXN][MAXN];//f[i][j]表示前i次翻转有j个位置合法的方案数。 char a[MAXN],b[MAXN]; inline void get_combination() { for(ll i=0;i<=n;++i)c[i][0]=1; for(ll i=1;i<=n;++i)c[i][1]=i; for(ll i=1;i<=n;++i) for(ll j=1;j<=i;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } signed main() { //freopen("1.in","r",stdin); n=read();k=read();m=read(); scanf("%s",a+1); scanf("%s",b+1); for(ll i=1;i<=n;++i) if(a[i]==b[i])++cnt; get_combination(); f[0][cnt]=1; for(ll i=1;i<=k;++i) { for(ll l=0;l<=n;++l)//枚举上一次状态 { if(!f[i-1][l])continue; for(ll j=0;j<=n;++j)//枚举当前状态 { if(abs(l-j)>m)continue; ll s1=abs(l-j); if((m-s1)&1)continue; ll s2=(m-s1)>>1; ll rest=n-l; if(j>=l) { if(s1+s2<=rest)f[i][j]=(f[i][j]+((f[i-1][l]*c[rest][s1+s2]%mod)*c[l][s2])%mod)%mod; } else if(s1+s2<=l)f[i][j]=(f[i][j]+((f[i-1][l]*c[rest][s2]%mod)*c[l][s1+s2])%mod)%mod; } } } printf("%lld\n",f[k][n]); return 0; }
LINK：系统设计想了2h都没思路的题目XR-round系列 才知道有这种题目的存在，好难想啊。
当时比赛的时候都没能想出来 一棵有根树每次指定一个节点开始沿着m这个序列向下跑问停止时到达哪个节点了？显然的nQ暴力，除此之外也就没有什么了。
但是呢$n,Q<=200000$这显然是不能过的，考虑一下正解？离线？因为还带修改所以基本上需要在线搞。
观察 修改的是什么m这个序列 我们从题目本身下手 修改这个序列是为了阻止我们暴力的干某件事情所以进行了修改。其实就算不修改我们离线之后尽管每个点都便利了一次但是最后的复杂度仍免不了是MQ的照样歇菜。
如何对于一棵树的某一条链和这个序列的l r进行快速匹配呢？我们发现了我们先对树的每一层进行标号 然后设根到某个节点x的路径上的字符串为sx那么发现了什么这个字符串最多有O(n)。
所以对于一次询问我们快速提取出l到r这个区间内的字符串再加上询问的从x出发的那个节点sx且如果存在我们就得到了目标节点的字符串信息了直接查找。
查找的话还是字符串hash比较好一点这样如果保证存在我们直接在主席树上找是否有这个值出现即可。但是如果不存在怎么办？这是一个比较严重的问题好像很难解决的样子，不过好像也是可以的考虑到答案必然是某个节点我们不妨二分一下深度 答案之上的节点我们必然也可以找到 所以显然二分是成立的。复杂度$Q(logn)^2$但是注意到一个问题带修改的m序列hash值也在变暴力一点直接线段树维护hash值结束..
但是太暴力了,写两棵树我不是很想写，看了题解 发现果然和题解差的好远，题解直接用线段树维护了hash值，然后查找直接线段树上二分省去了我那个二分的log然后判定的话直接hash表中进行判定。
真的是简洁，那么这道题就这样做即可。
原文：https://www.cnblogs.com/chdy/p/11552897.html
