Jan.20th
注：黑粗体为超链接
照题目要求模拟就行了
裸的扩欧
没有学过的童鞋戳右边→_→扩展欧几里得算法详解
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int exgcd(int a,int b,int &x,int &y){ if (b==0){x=1;y=0;return a;} int gcd=exgcd(b,a%b,x,y); int t=x; x=y;y=t-a/b*y; return gcd; } int A,B,C; int main(){ A=IN(),B=IN(),C=-1*IN(); int x,y; int gcd=exgcd(A,B,x,y); if (C%gcd!=0) return puts("-1"),0; ll s=C/gcd; printf("%I64d %I64d\n",s*x,s*y); } |
主要就是要在线性时间内求出所有的前缀是不是回文串
这个我们可以用扩展KMP搞
没有学过的童鞋戳右边→_→扩展KMP算法详解
然后我们把串S读进来 再反一下记为T
再把串T的后缀们与S做一下扩展KMP
如果对于串T存在$ex_i+i=len$那么也就是说：
在串S中$[ 0 , len-i+1 ]$这个前缀是回文串
然后剩下的就比较傻了
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } const int maxlen=5000005; char s[maxlen],t[maxlen]; int next[maxlen],ex[maxlen],len,lev[maxlen]; void GetNext(){ next[0]=len; int k=0; while (k<len-1&&s[k]==s[k+1]) k++; next[1]=k;k=1; Rep(i,2,len-1){ int p=k+next[k]-1,L=next[i-k]; if (i+L<=p) next[i]=L; else{ int j=max(p-i+1,0); while (i+j<len&&s[j]==s[i+j]) j++; next[i]=j; k=i; } } } void GetExtend(){ int k=0; while (k<len&&t[k]==s[k]) k++; ex[0]=k;k=0; Rep(i,1,len-1){ int p=k+ex[k]-1,L=next[i-k]; if (i+L<=p) ex[i]=L; else{ int j=max(p-i+1,0); while (i+j<len&&s[j]==t[i+j]) j++; ex[i]=j; k=i; } } } int main(){ gets(s); len=strlen(s);t[len]=0; Rep(i,0,len-1) t[i]=s[len-i-1]; GetNext();GetExtend(); int Ans=0; Rep(i,0,len-1){ if (ex[len-i-1]+len-i-1==len) lev[i]=lev[(i-1)/2]+1,Ans+=lev[i]; else lev[i]=0; } printf("%d\n",Ans); } |
Jan 27, 2024 05:31:22 PM
Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.