网站建设的发展目标,wordpress付费下载插件,网站欢迎页源码,wordpress中接入支付宝题目大意
对于一个长度为 n n n的 01 01 01字符串 S S S#xff0c;请求出将其分为至少 k k k段#xff0c;将每段看成二进制数求和后的最大值以及取到这个最大值的划分方案的数量。
输出最大值模 998244353 998244353 998244353后的值和划分方案的数量模 998244353 998244…题目大意
对于一个长度为 n n n的 01 01 01字符串 S S S请求出将其分为至少 k k k段将每段看成二进制数求和后的最大值以及取到这个最大值的划分方案的数量。
输出最大值模 998244353 998244353 998244353后的值和划分方案的数量模 998244353 998244353 998244353后的值。 1 ≤ n , k ≤ 2 × 1 0 6 1\leq n,k\leq 2\times 10^6 1≤n,k≤2×106 题解
如果前 k k k位没有 1 1 1则最优解一定是第一个 1 1 1之前所有间隔中选 k − 1 k-1 k−1个及以上的间隔因为把最后一段形成的二进制数从中间分开一定会减小可以用组合数来计算。如果一个 1 1 1都没有则最优解就是 n − 1 n-1 n−1个间隔中选 k − 1 k-1 k−1个及以上的间隔。
如果不满足上面的条件则最优解一定是选出一段长度为 n − k 1 n-k1 n−k1子串剩下的每一个数单独分一段。我们考虑比较两种划分方案的大小。
设第一种划分方案的 n − k 1 n-k1 n−k1的串看成的二进制数为 v 1 v_1 v1其余 k − 1 k-1 k−1段中 1 1 1的个数为 t 1 t_1 t1第二种划分方案的 n − k 1 n-k1 n−k1的串看成的二进制数为 v 2 v_2 v2其余 k − 1 k-1 k−1段中 1 1 1的个数为 t 2 t_2 t2。当 v 1 v 2 v_1v_2 v1v2时
如果 v 1 v_1 v1和 v 2 v_2 v2的前 n − k n-k n−k位相同而 v 1 v_1 v1的最后一位为 1 1 1 v 2 v_2 v2的最后一位为 0 0 0则 t 1 1 t 2 t_11t_2 t11t2两种划分方案的结果是相同的如果 v 1 v_1 v1和 v 2 v_2 v2的前 n − k n-k n−k位存在不同则设第一个不同的位为 t t t 如果 t 1 ≥ t 2 t_1\geq t_2 t1≥t2则显然第一种方案更优如果 t 1 t 2 t_1t_2 t1t2则我们将 S S S中的每个 1 1 1减去对答案的贡献 1 1 1两种划分方案的大小关系不变。此时其余 k − 1 k-1 k−1段中的 1 1 1都不算贡献最大段中每一个为 1 1 1的位 i i i的贡献为 2 i − 1 2^i-1 2i−1那么两种方案中前 t − 1 t-1 t−1个位置的贡献相同第一种方案中第 t t t位的贡献为 2 t − 1 2^t-1 2t−1而第二种划分方案中第 t t t位为 0 0 0之后的位之和小于等于 2 t − 1 2^t-1 2t−1因为每个 1 1 1的贡献都被减去了 1 1 1所以之后的位的贡献之和小于 2 t − 1 2^t-1 2t−1得第一种方案更优
由此可得以 1 , 2 , … , k 1,2,\dots,k 1,2,…,k开头长度为 n − k 1 n-k1 n−k1的串中划分出的串为字典序最大的串的结果最优。如果字典序最大的串的最后一位为 1 1 1前面 n − k n-k n−k位与其相同最后一位为 0 0 0的串也是最优的。
那我们怎么求字典序最大的串呢可以用二分哈希。从 1 1 1到 k k k枚举 i i i设 l l l为以 1 1 1到 i − 1 i-1 i−1为起点的串中字典序最大的串的起点那么对于当前的 i i i我们要比较 l l l开头的串和 i i i开头的串的字典序的大小。那么我们可以二分两个串最长的公共前缀假设公共前缀为 1 1 1到 t t t则 t 1 t1 t1即为两个串中第一个不同的位置比较这个位置的大小即可知道两个串的大小关系。用哈希可以 O ( 1 ) O(1) O(1)判断两个字符串是否相同所以处理一个 i i i的时间复杂度是 O ( log n ) O(\log n) O(logn)的。
求出字典序最大的串之后判断这个串的最后一位是否为 1 1 1。如果是的话将 1 1 1改为 0 0 0再判断以 1 , 2 , … , k 1,2,\dots,k 1,2,…,k开头长度为 n − k 1 n-k1 n−k1的串中是否有与这个修改后的串相同的这同样可以用哈希来 O ( 1 ) O(1) O(1)比较。
最大值可以用字典序最大的串对应的二进制数加其余部分的 1 1 1的个数来得到方案数可以在比较大小和是否相同的时候得到那么这道题就解决了。
注意要特判 n k nk nk的情况此时最大值为 S S S中 1 1 1的个数方案数为 1 1 1。
注意代码中虽然使用了单哈希但这样有一定可能将两个不同的串判断为相同的串有可能但可能性不大所以最好使用双哈希。
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
code
#includebits/stdc.h
using namespace std;
const int N2000000;
const long long mod998244353;
int n,k,len,sum[N5];
long long ans1,ans2,p[N5],pw[N5],jc[N5],ny[N5];
char s[N5];
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void init(){jc[0]1;pw[0]1;for(int i1;iN;i){jc[i]jc[i-1]*i%mod;pw[i]pw[i-1]*2%mod;}ny[N]mi(jc[N],mod-2);for(int iN-1;i0;i--) ny[i]ny[i1]*(i1)%mod;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
long long hsh(int l,int r){return (p[r]-p[l-1]*pw[r-l1]%modmod)%mod;
}
int gt(int i,int j){int l1,rlen,mid;while(lr){midlr1;if(hsh(i,imid-1)hsh(j,jmid-1)) lmid1;else rmid-1;}return l-1;
}
int main()
{
// freopen(divide.in,r,stdin);
// freopen(divide.out,w,stdout);init();scanf(%d%d,n,k);lenn-k1;scanf(%s,s1);for(int i1;in;i){sum[i]sum[i-1]s[i]-0;p[i](p[i-1]*2s[i]-0)%mod;}if(!sum[n]){for(int ik;in;i){ans2(ans2C(n-1,i-1))%mod;}printf(0 %lld,ans2);return 0;}if(kn){printf(%lld 1,sum[n]);return 0;}if(sum[n-len1]0){int fst1;while(s[fst]!1) fst;ans1hsh(fst,n);for(int ik;ifst;i){ans2(ans2C(fst-1,i-1))%mod;}printf(%lld %lld,ans1,ans2);return 0;}int l1;ans21;for(int i2;ilen-1n;i){int vtgt(l,i);if(vtlen) ans2;else if(s[lvt]s[ivt]){li;ans21;}}if(s[llen-1]1){int hs(hsh(l,llen-1)-1)%mod;for(int i1;ilen-1n;i){if(hshsh(i,ilen-1)) ans2;}}ans1hsh(l,llen-1)sum[l-1]sum[n]-sum[llen-1];printf(%lld %lld,ans1,ans2);return 0;
}
文章转载自： http://www.morning.qdmdp.cn.gov.cn.qdmdp.cn http://www.morning.kxryg.cn.gov.cn.kxryg.cn http://www.morning.kphyl.cn.gov.cn.kphyl.cn http://www.morning.xkbdx.cn.gov.cn.xkbdx.cn http://www.morning.ntgjm.cn.gov.cn.ntgjm.cn http://www.morning.guanszz.com.gov.cn.guanszz.com http://www.morning.wqmyh.cn.gov.cn.wqmyh.cn http://www.morning.jkcpl.cn.gov.cn.jkcpl.cn http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.zwznz.cn.gov.cn.zwznz.cn http://www.morning.flfdm.cn.gov.cn.flfdm.cn http://www.morning.trmpj.cn.gov.cn.trmpj.cn http://www.morning.xfxlr.cn.gov.cn.xfxlr.cn http://www.morning.dhmll.cn.gov.cn.dhmll.cn http://www.morning.thbqp.cn.gov.cn.thbqp.cn http://www.morning.zpnfc.cn.gov.cn.zpnfc.cn http://www.morning.fnkcg.cn.gov.cn.fnkcg.cn http://www.morning.bypfj.cn.gov.cn.bypfj.cn http://www.morning.gzttoyp.com.gov.cn.gzttoyp.com http://www.morning.kngqd.cn.gov.cn.kngqd.cn http://www.morning.rrjzp.cn.gov.cn.rrjzp.cn http://www.morning.shuanga.com.cn.gov.cn.shuanga.com.cn http://www.morning.zplzj.cn.gov.cn.zplzj.cn http://www.morning.rbkdg.cn.gov.cn.rbkdg.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.yhrfg.cn.gov.cn.yhrfg.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.bttph.cn.gov.cn.bttph.cn http://www.morning.tbqxh.cn.gov.cn.tbqxh.cn http://www.morning.mhpmw.cn.gov.cn.mhpmw.cn http://www.morning.xzqzd.cn.gov.cn.xzqzd.cn http://www.morning.jqwpw.cn.gov.cn.jqwpw.cn http://www.morning.xmwdt.cn.gov.cn.xmwdt.cn http://www.morning.nfccq.cn.gov.cn.nfccq.cn http://www.morning.ruyuaixuexi.com.gov.cn.ruyuaixuexi.com http://www.morning.fbpyd.cn.gov.cn.fbpyd.cn http://www.morning.mzqhb.cn.gov.cn.mzqhb.cn http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.wqfrd.cn.gov.cn.wqfrd.cn http://www.morning.jmmz.cn.gov.cn.jmmz.cn http://www.morning.stcds.cn.gov.cn.stcds.cn http://www.morning.smhtg.cn.gov.cn.smhtg.cn http://www.morning.rongxiaoman.com.gov.cn.rongxiaoman.com http://www.morning.dfdhx.cn.gov.cn.dfdhx.cn http://www.morning.zlxrg.cn.gov.cn.zlxrg.cn http://www.morning.chongzhanggui.cn.gov.cn.chongzhanggui.cn http://www.morning.njnqn.cn.gov.cn.njnqn.cn http://www.morning.jqhrk.cn.gov.cn.jqhrk.cn http://www.morning.yrngx.cn.gov.cn.yrngx.cn http://www.morning.zlsmx.cn.gov.cn.zlsmx.cn http://www.morning.clxpp.cn.gov.cn.clxpp.cn http://www.morning.drnjn.cn.gov.cn.drnjn.cn http://www.morning.rlsd.cn.gov.cn.rlsd.cn http://www.morning.gbrdx.cn.gov.cn.gbrdx.cn http://www.morning.ddtdy.cn.gov.cn.ddtdy.cn http://www.morning.zzjpy.cn.gov.cn.zzjpy.cn http://www.morning.pbpcj.cn.gov.cn.pbpcj.cn http://www.morning.rqhdt.cn.gov.cn.rqhdt.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.rkbly.cn.gov.cn.rkbly.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.zqzhd.cn.gov.cn.zqzhd.cn http://www.morning.hwprz.cn.gov.cn.hwprz.cn http://www.morning.mtrfz.cn.gov.cn.mtrfz.cn http://www.morning.hcszr.cn.gov.cn.hcszr.cn http://www.morning.zsrdp.cn.gov.cn.zsrdp.cn http://www.morning.ldzss.cn.gov.cn.ldzss.cn http://www.morning.jqbpn.cn.gov.cn.jqbpn.cn http://www.morning.sjsks.cn.gov.cn.sjsks.cn http://www.morning.kjfqf.cn.gov.cn.kjfqf.cn http://www.morning.mlcnh.cn.gov.cn.mlcnh.cn http://www.morning.xfmzk.cn.gov.cn.xfmzk.cn http://www.morning.dpbdq.cn.gov.cn.dpbdq.cn http://www.morning.fnczn.cn.gov.cn.fnczn.cn http://www.morning.rdzlh.cn.gov.cn.rdzlh.cn http://www.morning.lbxcc.cn.gov.cn.lbxcc.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.qmrsf.cn.gov.cn.qmrsf.cn http://www.morning.jpmcb.cn.gov.cn.jpmcb.cn
