遵义北京网站建设,六安百姓杂谈,做软件多少钱,时尚大气网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你个串sss#xff0c;让后把它重复无限次得到ttt#xff0c;定义前缀的价值为cnt0−cnt1cnt_0-cnt_1cnt0−cnt1#xff0c;求ttt的前缀价值为xxx的前缀个数#xff0c;若有无限多输出−1-1−1。
…传送门
文章目录题意思路题意
给你个串sss让后把它重复无限次得到ttt定义前缀的价值为cnt0−cnt1cnt_0-cnt_1cnt0−cnt1求ttt的前缀价值为xxx的前缀个数若有无限多输出−1-1−1。
思路
定义pre[i]pre[i]pre[i]为前iii个字符的价值。 如果pre[n]0pre[n]0pre[n]0那么说明每个串都独立如果至少一个pre[i]xpre[i]xpre[i]x那么说明他是有无限个输出−1-1−1否则就不存在输出000姐即可。 如果pre[n]!0pre[n]!0pre[n]!0那说明我们可以以pre[n]pre[n]pre[n]为基底将xxx缩小p∗pre[n]p*pre[n]p∗pre[n]让后再加上某一个前缀pre[i]pre[i]pre[i]即p∗pre[n]pre[i]xp*pre[n]pre[i]xp∗pre[n]pre[i]x转化一下px−pre[i]pre[n]p\frac{x-pre[i]}{pre[n]}ppre[n]x−pre[i]也就是当(x−pre[i])modpre[n]0(x-pre[i])\bmod pre[n]0(x−pre[i])modpre[n]0的时候贡献加一需要注意(x−pre[i])(x-pre[i])(x−pre[i])与pre[n]pre[n]pre[n]需要同号最后特判一下x0x0x0的情况就好啦。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,x;
char s[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--){scanf(%d%d%s,n,x,s1);int sum0,flag0;for(int i1;in;i){sums[i]0;sum-s[i]1;if(sumx) flag1;}if(sum0) { if(flag) puts(-1); else puts(0); continue; }int ans0,pre0;for(int i1;in;i){pres[i]0;pre-s[i]1;if(1ll*sum*(x-pre)0(x-pre)%sum0)ans;}printf(%d\n,ans(x0));}return 0;
}
/**/
