网站备案表格样本,oa系统办公软件排名,h5游戏源码网,东莞市做网站CSA49G XSY3315 因为判断两串是否本质不同只看某几项是不是好数#xff0c;与究竟是哪个好数无关#xff0c;所以考虑转换一下题意#xff1a; 给出一个长度为aka_kak的01串SSS#xff0c;第a1,a2,...,aka_1,a_2,...,a_ka1,a2,...,ak项为1#xff0c;其余项为0。 …CSA49G XSY3315 因为判断两串是否本质不同只看某几项是不是好数与究竟是哪个好数无关所以考虑转换一下题意 给出一个长度为aka_kak的01串SSS第a1,a2,...,aka_1,a_2,...,a_ka1,a2,...,ak项为1其余项为0。 现要用若干个SSS的前缀拼出串TTT使得TTT中有nnn个1以1结尾并且任意两个1之间0的个数不超过mmm。问所有不同的TTT的长度之和为多少
SSS如果用01串表示会很长发现kkk很小考虑换一种表示方式设biai−ai−1b_ia_i-a_{i-1}biai−ai−1。我们把SSS串描述成{b1,b2,b3,...,bk}\{b_1,b_2,b_3,...,b_k\}{b1,b2,b3,...,bk}表示SSS由 (b1−1)(b_1-1)(b1−1)个0,1个1,(b2−1)(b_2-1)(b2−1)个0,1个1,…,(bk−1)(b_k-1)(bk−1)个0,1个1 拼接而成。
设g(x,i)g(x,i)g(x,i)表示目前有xxx个1以 (bi−1)(b_i-1)(bi−1)个01个1 结尾的01串个数 f(x,i)f(x,i)f(x,i)表示目前有xxx个1以 (bi−1)(b_i-1)(bi−1)个01个1 结尾的01串长度之和。 可以列出dp式
g(x,i){g(x−1,i−1)i1∑j1kg(x−1,j)×(m−a[1]1)i1g(x,i)\begin{cases}g(x-1,i-1)\qquad i1\\\sum_{j1}^{k}g(x-1,j)\times(m-a[1]1)\qquad i1\end{cases}g(x,i){g(x−1,i−1)i1∑j1kg(x−1,j)×(m−a[1]1)i1
f(x,i){f(x−1,i−1)(a[i]−a[i−1])×g(x−1,i−1)i1∑j1kf(x−1,j)×(m−a[1]1)g(x−1,j)×(a[1]m)(m−a[1]1)2i1f(x,i)\begin{cases}f(x-1,i-1)(a[i]-a[i-1])\times g(x-1,i-1)\qquad i1\\\sum_{j1}^{k}f(x-1,j)\times(m-a[1]1)g(x-1,j)\times\frac{(a[1]m)(m-a[1]1)}{2}\qquad i1\end{cases}f(x,i){f(x−1,i−1)(a[i]−a[i−1])×g(x−1,i−1)i1∑j1kf(x−1,j)×(m−a[1]1)g(x−1,j)×2(a[1]m)(m−a[1]1)i1
把式子用矩阵快速幂优化一下复杂度是O(k3logn)O(k^3logn)O(k3logn) ps.因为fff的转移同时与f,gf,gf,g有关所以通过矩乘转移的过程有点特殊具体可以看代码。
然而还有一个小小的问题 假设a{2,6,7,9,13}a\{2,6,7,9,13\}a{2,6,7,9,13} 那么S[1−13]0100011010001S[1-13]0100011010001S[1−13]0100011010001S[1−6]010001S[1-6]010001S[1−6]010001S[1−7]0100011S[1-7]0100011S[1−7]0100011。 我们发现S[1−7]S[1−6]S[1−13]S[1-7]S[1-6]S[1-13]S[1−7]S[1−6]S[1−13]即若S[1−y]S[1-y]S[1−y]是S[1−x]S[1-x]S[1−x]的后缀则S[1−x]S[1-x]S[1−x]可以由S[1−y]S[1-y]S[1−y],S[1−(x−y)]S[1-(x-y)]S[1−(x−y)]拼成。但仔细看上面的dp式就会发现S[1−7]S[1−6]S[1-7]S[1-6]S[1−7]S[1−6]和S[1−13]S[1-13]S[1−13]被算成了两个串。怎么办暴力预处理一下对于前缀S[1−x]S[1-x]S[1−x]若有前缀S[1−y]S[1-y]S[1−y]同时是S[1−x]S[1-x]S[1−x]的后缀则前缀S[1−x]S[1-x]S[1−x]不能取。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int mod1e97;
const int K110;
int kk,m,n,a[K],pd[K][K],flag[K],ans;
struct Matrix{int n,m,g[K][K],f[K][K];//g:个数 f:长度和 Matrix(int x0,int y0){memset(f,0,sizeof(f));memset(g,0,sizeof(g));nx,my;}friend Matrix operator * (Matrix a,Matrix b){Matrix res(a.n,b.m);for(int i1;ia.n;i){for(int j1;jb.m;j){__int128 g0,f0;for(int k1;ka.m;k){g1ll*a.g[i][k]*b.g[k][j];f1ll*a.f[i][k]*b.g[k][j]1ll*a.g[i][k]*b.f[k][j];}res.g[i][j]int(g%mod);res.f[i][j]int(f%mod);}}return res;}
};
int Sum(ll x,ll y){return (xy)*(y-x1)/2%mod;
}
int main(){scanf(%d%d%d,kk,m,n);for(int i1;ikk;i) scanf(%d,a[i]);sort(a1,akk1);pd[1][1]1;for(int i2;ikk;i){int fl0;for(int j2;ji;j){if(pd[i-1][j-1]1) fl1;if(pd[i-1][j-1]1(a[j]-a[j-1])(a[i]-a[i-1])) pd[i][j]1;}if(a[1]a[i]-a[i-1]fl) pd[i][1]1;for(int j1;ji;j)if(pd[i][j]1) flag[i]1;}Matrix A(kk,kk),res(1,kk);for(int i1;ikk;i){if(flag[i]0){A.g[i][1]max(m-a[1]1,0);A.f[i][1]max(Sum(a[1],m),0);} }for(int i1;ikk;i){if(a[i1]-a[i]m){A.g[i][i1]1;A.f[i][i1]a[i1]-a[i];}}res.g[1][1]max(m-a[1]1,0);res.f[1][1]max(Sum(a[1],m),0);int bn-1;while(b){if(b1) resres*A;b1;AA*A;}for(int i1;ikk;i){if(flag[i]0) ans(ansres.f[1][i])%mod;}printf(%d\n,ans);return 0;
}
