P4173 残缺的字符串 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • hrbust_cx
    感谢博主QvQ
  • ghj1222
    巨佬啊!!!
  • orzage
    写得好棒啊!给dalao跪了!! 囧rz
  • 祥瑞御免
    orz
  • czpcf
    太精彩了!万分感谢!
  • laduiw
    fantastic
  • irakatz
    6
  • 蒟蒻wyx
    顶上去
作者: Ebola 更新时间: 2018-08-05 09:17  在Ta的博客查看 举报    22  

这是一道通配符匹配模板题。对于通配符的匹配,本人发表拙作如下。

浅谈FFT在字符串匹配中的应用

背景引入

字符串匹配,是OI中的一个古老为传统的问题。常见的匹配问题有:单模式串匹配、多模式串匹配、字串匹配。而对应的算法是KMP、AC自动机、后缀自动机。而我们今天要谈的问题,是单模式串匹配问题的一种:带通配符的单模式串匹配。

为了逐步解决这个问题,我们从普通的单模式串匹配开始说起。

普通的单模式串匹配

问题概述:给定模式串A(长度为m)、文本串B(长度为n),需要求出所有位置p,满足B串从第p个字符开始的连续m个字符,与A串完全相同

KMP是这一类问题的优秀算法,理论复杂度是线性的。但今天我们要用FFT来解决这个问题。千万不要因为FFT的复杂度高于KMP而忽略这一段,因为这一段内容对接下来我们要解决的问题而言,非常重要。

为了使问题更便于研究,我们约定所有字符串的下标从0开始

我们定义字符串的匹配函数C(x,y)=A(x)-B(y),那么我们可以形式化地定义“匹配”:若C(x,y)=0,则称A的第x个字符和B的第y个字符匹配。再定义完全匹配函数$P(x)=\sum\limits_{i=0}^{m-1}C(i,x-m+i+1)$,若P(x)=0,则称B以第x位结束的连续m位,与A完全匹配

但有没有觉得这个完全匹配函数有什么问题?似乎,根据完全匹配函数,“ab”与“ba”是匹配的???问题出在我们定义的匹配函数身上。匹配函数的确可以判断某一位是否匹配,但加了一个求和符号,一切都变了,只要两个串所含的字符是一样的,不管排列如何,完全匹配函数都会返回0值。

而这一切的罪魁祸首就是匹配函数的正负号!我们现在要做的是:定义一个更好的匹配函数,只要两个字符串某一位的匹配函数非零,完全匹配函数也不可能为零。不难想到给匹配函数加一个绝对值符号。但这样似乎就只能O(nm)暴力计算,没有更好的优化方法了。于是我们给匹配函数加上一个平方符号。此时完全匹配函数就是$P(x)=\sum\limits_{i=0}^{m-1}\left[A(i)-B(x-m+i+1)\right]^2$

这样还是没什么优化方法。我们不妨翻转A串,将翻转后的结果设为S。形式化地,S(x)=A(m-x-1)。据此不难推出A(x)-S(m-x-1)。于是完全匹配函数可以写成$P(x)=\sum\limits_{i=0}^{m-1}\left[S(m-i-1)-B(x-m+i+1)\right]^2$

大力展开这个函数:$P(x)=\sum\limits_{i=0}^{m-1}\left[S(m-i-1)^2+B(x-m+i+1)^2-2S(m-i-1)B(x-m+i+1)\right]$

再将求和符号拆开:$P(x)=\sum\limits_{i=0}^{m-1}S(m-i-1)^2+\sum\limits_{i=0}^{m-1}B(x-m+i+1)^2-2\sum\limits_{i=0}^{m-1}S(m-i-1)B(x-m+i+1)$

第一项是一个定值,可以O(m)预处理出来。第二项可以O(n)预处理前缀和。现在问题就在第三项。第三项中,两个小括号里面的东西加起来,似乎能抵消很多东西?居然……刚好等于x?这是巧合吗?当然不是,明明是我干出来的。所以,第三项是不是可以写成$-2\sum\limits_{i+j=x}S(i)B(j)$呢?当然可以!(这一步不太好解释,需要自己好好理解一下)

那么,我们设$T=\sum\limits_{i=0}^{m-1}S(i)^2\qquad f(x)=\sum\limits_{i=0}^xB(i)^2\qquad g(x)=\sum\limits_{i+j=x}S(i)B(j)$

于是就有$P(x)=T+f(x)-f(x-m)-2g(x)$

观察这个g函数,发现它不就是我们熟悉的卷积形式吗?而且还是最常规的卷积——多项式乘法!于是可以用FFT计算出g函数了!然后再代入计算一下,就可以O(n)得到所有P(x)的值了!

说了那么多,其实代码很短的。下面是核心代码。FFT相信大家都会,就不放出来了

void FFT_Match(char *s1,char *s2,int m,int n)
{
    for(int i=0;i<m;i++) A[i].r=s1[i]-'a'+1;
    for(int i=0;i<n;i++) B[i].r=s2[i]-'a'+1;
    reverse(A,A+m);double T=0;
    for(int i=0;i<m;i++) T+=A[i].r*A[i].r;
    f[0]=B[0].r*B[0].r;
    for(int i=1;i<n;i++) f[i]=f[i-1]+B[i].r*B[i].r;
    FFT(A,len,1);FFT(B,len,1);
    for(int i=0;i<len;i++) g[i]=A[i]*B[i];
    FFT(g,len,-1);
    for(int x=m-1;x<n;x++)
    {
        double P=T+f[x]-f[x-m]-2*g[x].r;
        if(fabs(P)<eps) printf("%d ",x-m+2);
    }
}

带通配符的单模式串匹配

问题概述:给定模式串A(长度为m)、文本串B(长度为n),串的某些字符是“通配符”(通配符是一种可以与任意字符匹配的字符)。需要求出所有位置p,满足B串从第p个字符开始的连续m个字符,与A串完全相同

这个问题显然用KMP就无法解决了,我们还是考虑和上面类似的方法。那么我们回顾上面的普通串匹配过程,我们可以总结出思路大概是这样的:

  1. 定义匹配函数

  2. 定义完全匹配函数

  3. 快速计算每一位的完全匹配函数值

有了通配符,我们肯定需要重新定义一个匹配函数

我们设通配符的数值为0,定义匹配函数$C(x,y)=[A(x)-B(y)]^2A(x)B(y)$,这样就完美地解决了通配符匹配问题。那么我们的完全匹配函数就是$P(x)=\sum\limits_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)$

还是老套路,将A串翻转,也就是设$S(i)=A(m-i-1)$

然后完全匹配函数变成:$P(x)=\sum\limits_{i=0}^{m-1}[S(m-i-1)-B(x-m+i+1)]^2S(m-i-1)B(x-m+i+1)$

暴力展开:$P(x)=\sum\limits_{i=0}^{m-1}S(m-i-1)^3B(x-m+i+1)+\sum\limits_{i=0}^{m-1}S(m-i-1)B(x-m+i+1)^3-2\sum\limits_{i=0}^{m-1}S(m-i-1)^2B(x-m+i+1)^2$

发现所有的项,都满足两个小括号加起来等于x,所以全部写成卷积的形式:

$P(x)=\sum\limits_{i+j=x}S(i)^3B(j)+\sum\limits_{i+j=x}S(i)B(j)^3-2\sum\limits_{i+j=x}S(i)^2B(j)^2$

这样只要做6次FFT外加1次IFFT就可以得到完全匹配函数每一位的值了

核心代码其实也不长,三次多项式乘法而已,常数略大

void FFT_match(char *s1,char *s2,int m,int n)
{
    reverse(ss1,ss1+m);
    for(int i=0;i<m;i++) A[i]=(s1[i]!='*')?(s1[i]-'a'+1):0;
    for(int i=0;i<n;i++) B[i]=(s2[i]!='*')?(s2[i]-'a'+1):0;

    for(int i=0;i<len;i++) a[i]=Comp(A[i]*A[i]*A[i],0),b[i]=Comp(B[i],0);
    FFT(a,len,1);FFT(b,len,1);
    for(int i=0;i<len;i++) P[i]=P[i]+a[i]*b[i];

    for(int i=0;i<len;i++) a[i]=Comp(A[i],0),b[i]=Comp(B[i]*B[i]*B[i],0);
    FFT(a,len,1);FFT(b,len,1);
    for(int i=0;i<len;i++) P[i]=P[i]+a[i]*b[i];

    for(int i=0;i<len;i++) a[i]=Comp(A[i]*A[i],0),b[i]=Comp(B[i]*B[i],0);
    FFT(a,len,1);FFT(b,len,1);
    for(int i=0;i<len;i++) P[i]=P[i]-a[i]*b[i]*Comp(2,0);

    FFT(P,len,-1);
    for(int i=m-1;i<n;i++) if(fabs(P[i].r)<=1e-7) printf("%d ",i-m+2);
}

本题直接套用上述代码即可。

评论

  • Neptune_Disaster
    Orz
  • M_sea
    Orz
  • pathogen
    Orz
  • jiuguaiwf
    orz
  • jiuguaiwf
    好厉害啊QwQ
作者: ⚡cdecl⚡ 更新时间: 2019-02-23 16:51  在Ta的博客查看 举报    15  

题意

传送门:洛谷 P4173 - 残缺的字符串

给你两个带通配符的串 $A, B$。问 $B$ 中可以匹配多少个 $A$,并输出匹配的开头位置。

看起来和 FFT 没关系?

解法

首先我们令通配符 * 为 $0$。

我们在两个长度相同的字符串 $A, B$ 上定义距离函数 $\operatorname{dist}(A, B)$ 为 $\sum_{i=0}^{n-1}(A_i - B_i)^2A_iB_i$。显然当 $\operatorname{dist}(A, B) = 0$ 时,$A = B$。

展开得 $\sum_{i=0}^{n-1} \left( {A_i}^3B_i - 2 {A_i}^2{B_i}^2 + A_i{B_i}^3 \right)$。

我们将 $A$ 翻转得到 $A'$,即令 $A'_i = A_{n-i-1}$。

那么上式等于 $\sum_{i=0}^{n-1} \left( {A'_{n-i-1}}^3B_i - 2 {A'_{n-i-1}}^2{B_i}^2 + A'_{n-i-1}{B_i}^3 \right)$。这明显是卷积的形式。

用 FFT 求三遍卷积,将所有位置为 $0$ 的下标输出即可。

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>

typedef double D;
const D P = acos(-1);
const int N = 2e6 + 62;

struct $ {
    D x, y;
    inline $(D x_ = 0, D y_ = 0) : x(x_), y(y_) {}
    inline $ operator+(const $& rhs) const { return $(x + rhs.x, y + rhs.y); }
    inline $ operator-(const $& rhs) const { return $(x - rhs.x, y - rhs.y); }
    inline $ operator*(const $& rhs) const { return $(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
    inline $ operator/(D rhs) const { return $(x / rhs, y / rhs); }
};

int lim, l, r[N];
void fft($* a, int op) {
    for (int i = 0; i < lim; i++)
        if (i < r[i]) std::swap(a[i], a[r[i]]);
    for (int i = 1; i < lim; i <<= 1) {
        $ wn(cos(P / i), op * sin(P / i));
        for (int j = 0; j < lim; j += i << 1) {
            $ w(1);
            for (int k = 0; k < i; k++, w = w * wn) {
                $ x = a[j + k], y = w * a[i + j + k];
                a[j + k] = x + y;
                a[i + j + k] = x - y;
            }
        }
    }
    if (op == -1)
        for (int i = 0; i < lim; i++) a[i] = a[i] / lim;
}

$ a2[N], b2[N], c[N];
int m, n, a[N], b[N];
std::queue<int> q;
char s1[N], s2[N];
int main() {
    scanf("%d%d%s%s", &m, &n, s1, s2);
    for (lim = 1; lim < n * 2; lim <<= 1) l++;
    for (int i = 1; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for (int i = 0; i < m; i++)
        if (s1[m - i - 1] != '*') a[i] = s1[m - i - 1] - 'a' + 1;
    for (int i = 0; i < n; i++)
        if (s2[i] != '*') b[i] = s2[i] - 'a' + 1;

    for (int i = 0; i < m; i++) a2[i] = $(a[i] * a[i] * a[i]);
    for (int i = 0; i < n; i++) b2[i] = $(b[i]);
    fft(a2, 1), fft(b2, 1);
    for (int i = 0; i < lim; i++) c[i] = a2[i] * b2[i];

    for (int i = 0; i < lim; i++) a2[i] = b2[i] = $();
    for (int i = 0; i < m; i++) a2[i] = $(a[i] * a[i]);
    for (int i = 0; i < n; i++) b2[i] = $(b[i] * b[i]);
    fft(a2, 1), fft(b2, 1);
    for (int i = 0; i < lim; i++) c[i] = c[i] - a2[i] * b2[i] * 2;

    for (int i = 0; i < lim; i++) a2[i] = b2[i] = $();
    for (int i = 0; i < m; i++) a2[i] = $(a[i]);
    for (int i = 0; i < n; i++) b2[i] = $(b[i] * b[i] * b[i]);
    fft(a2, 1), fft(b2, 1);
    for (int i = 0; i < lim; i++) c[i] = c[i] + a2[i] * b2[i];

    fft(c, -1);
    for (int i = m - 1; i < n; i++)
        if (fabs(c[i].x) < 0.5) q.push(i - m + 2);
    for (printf("%lu\n", q.size()); !q.empty(); q.pop()) printf("%d ", q.front());
}

评论

  • 还没有评论
作者: qiyue7 更新时间: 2018-12-03 19:01  在Ta的博客查看 举报    4  

Shift-or字符串匹配

这个经典的通配符问题可以直接转化为朴素的非确定性多模式匹配问题,那么就可以用Shift-or算法求解。Shift-or算法是位并行算法,位并行利用了计算机机器字位运算的内在并行性,可以把多个值装入同一个长度为w的机器字内,然后只需一次运算就能更新所有值。利用位并行,一个算法所执行的运算次数最多能减少到原来的1/W,这里W是机器字的位数。我们先预处理出模板串的每个字符出现在的位置,0表示已经出现,1表示未出现,然后再出现的地方默认26个字母全部出现,在读入匹配串时每一轮都目前已保留的状态的bitset取或,当且仅当已经匹配的长度为模板串长度时答案++,复杂度O(n^2/机器字位数),洛谷似乎是64位机器字,那么复杂度30w30w/64=1.4^10次位运算,根据换算1Ghz的cpu1秒1^10的位运算处理能力,给6s的时限随便跑跑就过了。

#include <bits/stdc++.h>
using namespace std;
bitset<300005> part[26],cur;
list<int> ans2;
int main()
{
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    string c, d;
    cin >> c >> d;
    cur.set();
    for (int i = 0; i < 26; ++i)
        part[i].set();
    for (int i = 0; i < a; ++i)
    {
        if (c[i] != '*')
            part[c[i] - 'a'].reset(i);
        else
            for (int j = 0; j < 26; ++j)
                part[j].reset(i);
    }
    int ans = 0;
    for (int i = 0; i < b; ++i)
    {
        if (d[i] != '*')
            cur = cur << 1 | part[d[i] - 'a'];
        else
            cur = cur << 1;
        if (cur[a-1] == 0)
        {
            ans++;
            ans2.push_back(i-a+2);
        }
    }
    cout << ans << '\n';
    if (ans > 0)
        for (auto &s : ans2)
            cout<<s<<" ";
    return 0;
}

评论

  • 还没有评论
作者: Ameyax 更新时间: 2018-03-09 10:07  在Ta的博客查看 举报    5  

没人发标算,%楼下大佬

把$*$都改成$0$
设$dis(A,B)=\sum\limits_{i=0}^{n-1}(A[i]-B[i])^2A[i]B[i]$

$B$以$i$结尾的串与$A$完全匹配的条件是$f[i]=dis(A,B[i-m+1,i])==0$

翻转$A$串,并在末尾补$0$。

$$f[i]=\sum\limits_{j=0}^i(A[j]-B[i-j])^2A[j]B[i-j]$$

$$=\sum\limits_{j=0}^iA[j]^3B[i-j]-2\sum\limits_{j=0}^iA[j]^2B[i-j]^2+\sum\limits_{j=0}^iA[j]B[i-j]^3$$

分三次$fft$出所有的$f[i]$,时间复杂度也是$O(nlogn)$但是比楼下大佬多了个$3$

代码常数巨大

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
const int MAX = 1100000;
char sa[MAX], sb[MAX];
int m, n, N, top, a[MAX], b[MAX];
int rev[MAX], sta[MAX];
struct cpx
{
    double x, y;
    cpx() {}
    cpx(double xx, double yy) { x = xx, y = yy; }
    friend cpx operator * (cpx a, cpx b)
    {
        return cpx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
    }
    friend cpx operator / (cpx a, double b)
    {
        return cpx(a.x / b, a.y / b);
    }
    friend cpx operator + (cpx a, cpx b)
    {
        return cpx(a.x + b.x, a.y + b.y);
    }
    friend cpx operator - (cpx a, cpx b)
    {
        return cpx(a.x - b.x, a.y - b.y);
    }
    friend cpx operator * (cpx a, double b)
    {
        return cpx(a.x * b, a.y * b);
    }
};
cpx A[MAX], B[MAX], C[MAX];
void fft(cpx *a, int f)
{
    for (int i = 0; i < N; i++)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 1; i < N; i <<= 1)
    {
        cpx wn(cos(pi / i), f * sin(pi / i));
        for (int j = 0; j < N; j += (i << 1))
        {
            cpx w(1, 0);
            for (int k = 0; k < i; k++)
            {
                cpx x = a[j + k], y = w * a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
                w = w * wn;
            }
        }
    }
    if (f == -1)
        for (int i = 0; i < N; i++)
            a[i] = a[i] / N;
}
int main()
{
    scanf("%d%d%s%s", &m, &n, sa, sb);
    int l = 0;
    for (N = 1; N < 2 * n; N <<= 1) l++;
    for (int i = 0; i < N; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for (int i = 0; i < m; i++)
        if (sa[i] != '*')
            a[i] = sa[i] - 'a' + 1;
    for (int i = 0; i < n; i++)
        if (sb[i] != '*')
            b[i] = sb[i] - 'a' + 1;
    reverse(a, a + m);
    for (int i = 0; i < m; i++) A[i] = cpx(a[i] * a[i] * a[i], 0);
    for (int i = 0; i < n; i++) B[i] = cpx(b[i], 0);
    fft(A, 1); fft(B, 1);
    for (int i = 0; i < N; i++) C[i] = C[i] + A[i] * B[i];

    for (int i = 0; i < N; i++) A[i] = B[i] = cpx(0, 0);
    for (int i = 0; i < m; i++) A[i] = cpx(a[i] * a[i], 0);
    for (int i = 0; i < n; i++) B[i] = cpx(b[i] * b[i], 0);
    fft(A, 1); fft(B, 1);
    for (int i = 0; i < N; i++) C[i] = C[i] - A[i] * B[i] * 2.0;

    for (int i = 0; i < N; i++) A[i] = B[i] = cpx(0, 0);
    for (int i = 0; i < m; i++) A[i] = cpx(a[i], 0);
    for (int i = 0; i < n; i++) B[i] = cpx(b[i] * b[i] * b[i], 0);
    fft(A, 1); fft(B, 1);
    for (int i = 0; i < N; i++) C[i] = C[i] + A[i] * B[i];

    fft(C, -1);
    for (int i = m - 1; i < n; i++)
        if (fabs(C[i].x) < 0.5)
            sta[++top] = i - m + 2;
    printf("%d\n", top);
    for (int i = 1; i <= top; i++)
        printf("%d ", sta[i]);
    return 0;
}

这题开6秒是闹哪样,bzoj上我用std::complex<double>都T掉了
上面的代码在bzoj跑了9s卡过

评论

  • boshi
    hack你:https://paste.ubuntu.com/p/sGfwCwrrr7/
作者: santongding 更新时间: 2018-03-03 00:52  在Ta的博客查看 举报    4  

好像没有题解。。。那我就说一说我的玄学做法

比较容易就能得出,如果将模板串翻转位置之后,不足的位置补零再与要匹配的串做fft,那么得出的多项式中F[ i ]是所有下标之和为i的两个字符的乘积,而由于模板串后边的位置被补零,所以能够找到n-m个F[i]表示所有匹配情况;(当然不必要真的补零,我大概觉着会好想一些吧。。。)

接下来考虑怎么判断每个情况是否合法,将模板串中26个字母都设为一个数,再将匹配串中所有字母设为倒数,如果有“*”号那么设为0,那么得出的每个表示匹配情况的值如果是个整数,就是合法的,如果不是就不合法;

当然这样很有可能有精度问题,所以得给每个字符一开始的值加一个数,似乎加个1000左右的数就可以,加个100以内的可能会被卡;

至于判断是否是整数时,实测1e-6也是可以过;

总之这个做法比较玄学,但唯一的好处是只需要做一次fft,跑得比较快

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define random(a,b) (a+rand()%(b-a+1))
#define pi 3.141592653589793238460643383279
const int maxn=1048577;
int n,m;
int nn=1,tk=0;
int a[maxn],b[maxn],c[maxn];
double abs(double x)
{
    if(x<0)return -x;
    return x;
} 
struct com
{
    double r,i;
    com(){
        r=i=0.0;
    }
    com(double x,double y){
        r=x,i=y;    
    } 
    com operator +(const com &o)const{
        return com(r+o.r,i+o.i);
    }
    com operator -(const com &o)const{
        return com(r-o.r,i-o.i);
    }
    com operator *(const com &o)const{
        return com(r*o.r-i*o.i,r*o.i+i*o.r);
    }
    com operator /(const double &o)const{
        return com(r/o,i/o);
    }
}c1[maxn],c2[maxn], omega[maxn];
void read(register int *t,int len)
{
    char s;
    for(register int i=0;i<len;i++)
    {
        s=getchar();
        while(!isdigit(s))s=getchar();
        t[i]=s-'0';
    }
}
void swap(com &x,com &y)
{
    com z=x;
    x=y;
    y=z;
}
void FFT(com *p)
{
    for(register int i=0,j=0; i<nn; i++)
    {
        if(i>j)swap(p[i],p[j]);
        for(register int l=nn>>1; (j^=l)<l; l>>=1);
    }
    for(register int l=2;l<=nn;l<<=1)
    {
        int mid=l/2;
        for(com *t=p;t!=p+nn;t+=l)
        for(register int i=0;i<mid;i++)
        {
            com tp=omega[nn/l*i] * t[i+mid];
            t[i+mid]=t[i]-tp;
            t[i]=t[i]+ tp;
        }
    }
}
com f[maxn],g[maxn];
int suma=0,sumb=0;
char sb[maxn];
int ans[maxn];
int anstot=0;
int main()
{
    scanf("%d%d",&m,&n);
    scanf("%s",sb);
    for(int i=0;i<m;i++)
    {
        if(sb[i]=='*')f[m-1-i].r=0.0,sumb++;
        else f[m-1-i].r=(double)(sb[i]-'a'+1000);
    }
    scanf("%s",sb);
    for(int i=0;i<n;i++)
    {
        if(sb[i]=='*')g[i].r=0.0;
        else g[i].r=1.0/(double)(sb[i]-'a'+1000);   
    } 
    while(nn<m+n-1)nn<<=1;
    for(register int i=0;i<nn;i++)omega[i]=com(std::cos(2.0*pi/(double)nn*(double)(i)),std::sin(2.0*pi/(double)nn*(double)i));
    FFT(f);
    FFT(g);
    for(register int i=0;i<nn;i++)
    {
        omega[i].i*=-1;
        f[i]=f[i]*g[i];
    }
    FFT(f);
    for(register int i=0;i<nn;i++)
        f[i].r/=(double)nn;
    for(int i=m-1;i<n;i++)
    {
        int tmp=(int)(f[i].r+0.5);//四舍五入
        if(abs(f[i].r-(double)tmp)<=1e-6)ans[++anstot]=i-m+2;
    }
    printf("%d\n",anstot);
    for(int i=1;i<=anstot;i++)printf("%d ",ans[i]); 
        return 0;
} 

正解好像得拆开证一波。。。感觉我这种做法很容易被卡啊orz

UPD:本来没开o2在洛谷被前边几个开了o2的碾压,遂开一波o2强行rk1,毕竟我fft只需要做一次,手残大常数也无所谓orz

 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。