QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#192226 | #7516. Robot Experiment | ucup-team1525# | WA | 0ms | 22196kb | C++14 | 2.5kb | 2023-09-30 13:59:15 | 2023-09-30 13:59:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll=long long;
const int N = 1e6;
const int m1 = 998244353;
const int m2 = 1e9 + 7;
int ksm(ll x,int tp,int p,int s=1){
for(;tp;x=x*x%p,tp>>=1) if(tp&1) s=x*s%p;
return s;
}
pii operator+(const pii &x, const pii &y)
{
return {(x.first + y.first) % m1, (x.second + y.second) % m2};
}
pii operator-(const pii &x, const pii &y)
{
return {(x.first - y.first + m1) % m1, (x.second - y.second + m2) % m2};
}
pii operator*(const pii &x, const int &t)
{
return {1ll * x.first * t % m1, 1ll * x.second * t % m2};
}
pii operator*(const pii &x, const pii &y)
{
return {1ll * x.first * y.first % m1, 1ll * x.second * y.second % m2};
}
pii ksm(pii x, int y)
{
pii ret = {1, 1};
while (y)
{
if (y & 1)
ret = ret * x;
x = x * x;
y >>= 1;
}
return ret;
}
const int v1=233,v2=137;
int n,m;
char s[N + 5], t[N + 5];
pii kp[N+5];
pii vs[N+5],vt[N+5];
int L[N+5];
int f[N+5][3],sf[N+5][3];
int add(int x,int y){ return (x+=y)>m1?x-m1:x; }
int sub(int x,int y){ return (x-=y)<0?x+m1:x; }
void prep()
{
kp[0]={1,1}; kp[1]={v1,v2};
for(int i=2;i<=N;i++)
kp[i]=kp[i-1]*kp[1];
}
bool chk(int l1,int r1,int l2,int r2){
return vs[r1]-vs[l1-1]*kp[r1-l1+1]==vt[r2]-vt[l2-1]*kp[r2-l2+1];
}
int query(int l1,int l2){
int l=0,r=min(n-l1,m-l2),mid;
while(l<=r){
mid=l+r>>1;
if(chk(l1,l1+mid,l2,l2+mid)) l=mid+1;
else r=mid-1;
}
return l;
}
void findL(){
for(int i=1;i<=n;i++){
int l1=query(i,1);
if(i+l1>n||1+l1>m) L[i]=l1;
else L[i]=l1+1+query(i+l1+1,2+l1)+1;
}
}
int main()
{
scanf("%s", s + 1);
scanf("%s", t + 1);
n = strlen(s + 1);
m = strlen(t + 1);
prep();
vs[0]={1,1};
for(int i=1;i<=n;i++)
vs[i]=vs[i-1]*kp[1]+pii{s[i]-'a',s[i]-'a'};
vt[0]={1,1};
for(int i=1;i<=m;i++)
vt[i]=vt[i-1]*kp[1]+pii{t[i]-'a',t[i]-'a'};
findL();
for(int i=1;i<=n;i++)
printf("%d ",L[i]);
puts("");
f[n+1][0]=1; sf[n+1][0]=1;
for(int i=n;i;i--){
f[i][0]=sub(sf[i+1][0],sf[i+L[i]][0]);
f[i][1]=sub(add(f[i][0],sf[i+1][1]),sf[i+L[i]][1]);
f[i][2]=add(sub(sf[i+1][2],sf[i+L[i]][2]),sub(add(f[i][1],f[i][1]),sf[i][0]));
for(int j=0;j<2;j++)
sf[i][j]=add(f[i][j],sf[i+1][j]);
}
printf("%d\n",f[1][2]);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 22196kb
input:
2 RU
output:
2 2
result:
wrong answer 1st lines differ - expected: '4', found: '2 '