QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#192226#7516. Robot Experimentucup-team1525#WA 0ms22196kbC++142.5kb2023-09-30 13:59:152023-09-30 13:59:15

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 13:59:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22196kb
  • [2023-09-30 13:59:15]
  • 提交

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 '