首页 > 代码库 > 【Codevs 1376】帕秋莉?诺蕾姬

【Codevs 1376】帕秋莉?诺蕾姬

http://codevs.cn/problem/1376/

枚举修改哪两位,将sum减去之前位置的数+交换之后  %m==0即可

预处理26的次方+O(n^2)

// <1376.cpp> - Tue Oct 18 21:50:03 2016// This file is made by YJinpeng,created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>using namespace std;typedef long long LL;const int MAXN=2010;char s[MAXN];int mul[MAXN];int main(){    freopen("1376.in","r",stdin);    freopen("1376.out","w",stdout);    scanf("%s",s);    int n=strlen(s),sum=0,m;    mul[n-1]=1;scanf("%d",&m);    for(int i=n-1;i;i--)        (sum+=mul[i]*(s[i]-A)%m)%=m,mul[i-1]=mul[i]*26%m;    (sum+=mul[0]*(s[0]-A)%m)%=m;    if(sum==0){printf("0 0");return 0;}    for(int i=0;i<n;i++)        for(int j=i+1;j<n;j++){            if(((sum+(s[i]-A)*(mul[j]-mul[i]+m)%m)%m+(s[j]-A)*(mul[i]-mul[j]+m)%m)%m==0){                printf("%d %d",i+1,j+1);return 0;            }        }printf("-1 -1");     return 0;}

 

【Codevs 1376】帕秋莉?诺蕾姬