一个正常人是不会做这种题的...

某年某月某天，我校机房有个可怜人被人强行立了个flag:9月月底做不出来luoguP2482就女装！于是他拼命的调代码。5分，10分，25分......95分。最后实在不行了求救了机房大佬WY才AC。

这位同志的精神感动了机房，于是全机房都开始疯狂的调这道题。我也不幸幸运的成为了其中的一员。

其实这道题就是模拟，大概是因为我平时闲的没事喜欢做游戏，所以感觉挺简单的。

把各种行为封装成自由函数，当然如果你想建class也没有问题。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

/*
¡¾ÌÒ¡¿ P
¡¾É±¡¿ K
¡¾ÉÁ¡¿ D
¡¾¾ö¶·¡¿ F
¡¾ÄÏÂùÈëÇÖ¡¿ N
¡¾Íò¼ýÆë·¢¡¿ W
¡¾ÎÞи¿É»÷¡¿ J
¡¾Öî¸ðÁ¬åó¡¿ Z
*/

const int MAX_PLAYER_NUM = 100 + 5;
const int MAX_CARD_NUM = 2000 + 5;
class PIG
{
public:
    int        card_num;
    int        life_num;
    int        _next;
    int        _last;
    char    identity;
    char    card[MAX_CARD_NUM];
    bool    isGetedZgln;
} A[MAX_PLAYER_NUM];
char    id_in_king[MAX_PLAYER_NUM];     //在主公眼里诸猪的身份
char    card_set[MAX_CARD_NUM];
char    scanner[MAX_PLAYER_NUM];
int        n, m, bad_man_num;
bool    GG;  //主公是否GG

inline     void        initt(                             );
inline     void        start(                            );
inline     void        mopai(       int fuck       );  //不知道怎么命名了...
inline     void        nmrqq(         int fuck       );
inline     void        wjqff(         int fuck       );
inline     void        jisha( int Killer, int GGer );
inline     void        killl( int Killer, int GGer );
inline     void        jdddd( int Killer, int GGer );
inline     bool        wxkjj(int x1, int x2, int x3);   //为了对齐

signed main()
{
    initt();
    start();
    if (A[1].life_num <= 0)    puts("FP");
    else puts("MP");
    for (int i = 1; i <= n; ++i)
    {
        if (A[i].life_num <= 0)    puts("DEAD");
        else
        {
            for (int j = 1; j <= A[i].card_num; ++j)
                if (A[i].card[j] != 'U')    printf("%c ", A[i].card[j]);
            puts("");
        }
    }
    return 0;
}

inline void    initt()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)    A[i]._next = i + 1, A[i]._last = i - 1;
    A[n]._next = 1, A[1]._last = n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j < MAX_CARD_NUM; ++j)    A[i].card[j] = 'U';
        scanf("%s", scanner);
        A[i].identity = scanner[0];
        for (int j = 1; j < 5; ++j)    scanf("%s", scanner), A[i].card[j] = scanner[0];
        A[i].life_num = A[i].card_num = 4;
        if (A[i].identity == 'F')    bad_man_num++;
        A[i].isGetedZgln = false;
    }
    id_in_king[1] = 'M';
    for (int i = 2; i <= n; ++i)    id_in_king[i] = 'U';
    for (int i = 1; i <= m; ++i)    scanf("%s", scanner), card_set[m - i + 1] = scanner[0];
}

inline void start()
{
    char now_card;
    GG = true;
    if (bad_man_num) GG = false;
    if (GG)        return;
    for (int i = 1; i; i = A[i]._next)
    {
        mopai(i), mopai(i);
        bool isKilled = true;
        for (int j = 1; j <= A[i].card_num; ++j)
        {
            if (A[i].card[j] != 'U')
            {
                if (!A[i].life_num)    break;
                now_card = A[i].card[j];

                if (now_card == 'P')
                {
                    if (A[i].life_num != 4)    A[i].life_num++, A[i].card[j] = 'U';
                    continue;
                }

                if (now_card == 'K')
                {
                    if (!isKilled && !A[i].isGetedZgln)    continue;
                    if ((A[i].identity == 'M') && (id_in_king[A[i]._next] != 'L') && (id_in_king[A[i]._next] != 'F'))
                        continue;
                    if ((A[i].identity == 'Z') && (id_in_king[A[i]._next] != 'F'))
                        continue;
                    if ((A[i].identity == 'F') && (id_in_king[A[i]._next] != 'Z') && (id_in_king[A[i]._next] != 'M'))
                        continue;
                    A[i].card[j] = 'U';
                    killl(i, A[i]._next);
                    id_in_king[i] = A[i].identity;
                    isKilled = false;
                    if (GG)    return;
                    continue;
                }

                if (now_card == 'F')
                {
                    if (A[i].identity == 'F')
                    {
                        A[i].card[j] = 'U';
                        jdddd(i, 1);
                        id_in_king[i] = A[i].identity;
                        if (GG)    return;
                        j = 0;
                        continue;
                    }
                    for (int k = A[i]._next; k != i; k = A[k]._next)
                    {
                        if ((A[i].identity == 'M' && (id_in_king[k] == 'L' || id_in_king[k] == 'F')) || (A[i].identity == 'Z' && id_in_king[k] == 'F'))
                        {
                            A[i].card[j] = 'U';
                            jdddd(i, k);
                            id_in_king[i] = A[i].identity;
                            if (GG)    return;
                            j = 0;
                            break;
                        }
                    }
                    continue;
                }


                if (now_card == 'N')
                {
                    A[i].card[j] = 'U';
                    nmrqq(i);
                    if (GG)    return;
                    j = 0;
                    continue;
                }

                if (now_card == 'W')
                {
                    A[i].card[j] = 'U';
                    wjqff(i);
                    if (GG)    return;
                    j = 0;
                    continue;
                }

                if (now_card == 'Z')
                {
                    A[i].isGetedZgln = true;
                    A[i].card[j] = 'U';
                    j = 0;
                    continue;
                }
            }
        }
    }
}

inline void mopai(int fuck)
{
    if (!m)    m++;
    A[fuck].card[++A[fuck].card_num] = card_set[m];
    m--;
}

inline void nmrqq(int fuck)
{
    for (int shit = A[fuck]._next; shit != fuck; shit = A[shit]._next)
    {
        if (!wxkjj(fuck, shit, 1))
        {
            int i;
            for (i = 1; i <= A[shit].card_num; ++i)
            {
                if (A[shit].card[i] == 'K')
                {
                    A[shit].card[i] = 'U';
                    break;
                }
            }
            if (i > A[shit].card_num)
            {
                A[shit].life_num--;
                if (shit == 1 && id_in_king[fuck] == 'U')    id_in_king[fuck] = 'L';
                if (!A[shit].life_num) jisha(fuck, shit);
                if (GG)    return;
            }
        }
    }
}

inline void wjqff(int fuck)
{
    for (int shit = A[fuck]._next; shit != fuck; shit = A[shit]._next)
    {
        if (!wxkjj(fuck, shit, 1))
        {
            int i;
            for (i = 1; i <= A[shit].card_num; ++i)
            {
                if (A[shit].card[i] == 'D')
                {
                    A[shit].card[i] = 'U';
                    break;
                }
            }
            if (i > A[shit].card_num)
            {
                A[shit].life_num--;
                if (shit == 1 && id_in_king[fuck] == 'U')    id_in_king[fuck] = 'L';
                if (!A[shit].life_num)    jisha(fuck, shit);
                if (GG)    return;
            }
        }
    }
}

inline void jisha(int Killer, int GGer)
{
    for (int i = 1; i <= A[GGer].card_num; ++i)
    {
        if (A[GGer].card[i] == 'P')
        {
            A[GGer].card[i] = 'U';
            A[GGer].life_num++;
            return ;
        }
    }

    A[A[GGer]._next]._last = A[GGer]._last;
    A[A[GGer]._last]._next = A[GGer]._next;

    if (GGer == 1)
    {
        GG = true;
        return ;
    }

    if (A[GGer].identity == 'F')    bad_man_num--;

    if (!bad_man_num)
    {
        GG = true;
        return ;
    }

    if (A[GGer].identity == 'F')    mopai(Killer), mopai(Killer), mopai(Killer);

    if (A[GGer].identity == 'Z' && A[Killer].identity == 'M')    A[Killer].card_num = 0, A[Killer].isGetedZgln = false;
}

inline void killl(int Killer, int GGer)
{
    for (int i = 1; i <= A[GGer].card_num; ++i)
    {
        if (A[GGer].card[i] == 'D')
        {
            A[GGer].card[i] = 'U';
            return ;
        }
    }
    A[GGer].life_num--;
    if (!A[GGer].life_num)    jisha(Killer, GGer);
}

inline void jdddd(int Killer, int GGer)
{
    int fuck, shit;
    if (wxkjj(Killer, GGer, 1))    return ;

    if (Killer == 1 && A[GGer].identity == 'Z')
    {
        A[GGer].life_num--;
        if (!A[GGer].life_num)    jisha(Killer, GGer);
        return ;
    }

    fuck = shit = 1;

    while (233)
    {
        while (A[GGer].card[fuck] != 'K' && fuck <= A[GGer].card_num)    ++fuck;
        if (fuck > A[GGer].card_num)
        {
            A[GGer].life_num--;
            if (!A[GGer].life_num)    jisha(Killer, GGer);
            return ;
        }
        else A[GGer].card[fuck] = 'U';

        while (A[Killer].card[shit] != 'K' && shit <= A[Killer].card_num)    ++shit;
        if (shit > A[Killer].card_num)
        {
            A[Killer].life_num--;
            if (!A[Killer].life_num)    jisha(GGer, Killer);
            return ;
        }
        else A[Killer].card[shit] = 'U';
    }
}

inline bool wxkjj(int x1, int x2, int x3)
{
    int i = x1;
    while (233)
    {
        if (x3 == 1)
        {
            if (id_in_king[x2] == A[i].identity || (id_in_king[x2] == 'M' && A[i].identity == 'Z') || (id_in_king[x2] == 'Z' && A[i].identity == 'M'))
            {
                for (int j = 1; j <= A[i].card_num; ++j)
                {
                    if (A[i].card[j] == 'J')
                    {
                        A[i].card[j] = 'U';
                        id_in_king[i] = A[i].identity;
                        return !wxkjj(i, x1, 0);
                    }
                }
            }
        }

        else
        {
            if (((A[i].identity == 'M' || A[i].identity == 'Z') && id_in_king[x1] == 'F') || (A[i].identity == 'F' && (id_in_king[x1] == 'M' || id_in_king[x1] == 'Z')))
            {
                for (int j = 1; j <= A[i].card_num; ++j)
                {
                    if (A[i].card[j] == 'J')
                    {
                        A[i].card[j] = 'U';
                        id_in_king[i] = A[i].identity;
                        return !wxkjj(i, x1, 0);
                    }
                }
            }
        }
        i = A[i]._next;
        if (i == x1)    break;
    }
    return false;
}

这次的CSP是十分伤心的，考试的状态不好，导致分数不理想。

睡了一觉后我重做了一下这四道题，觉得还是蛮简单的，于是便有了这篇题解。

T1

统计1的数量，字符串模拟即可

#include <bits/stdc++.h>

using namespace std;

char buf[233];

signed main() {
    fgets(buf, 233, stdin);
    int res = 0;
    for (int i = 0; i < 8; ++i)
        res += (buf[i] == '1');
    printf("%d", res);
}

T2

这道题是最亏的，STL是个好东西，但容易遗忘一些细节。比如erase后没有减掉下标。

模拟即可，用一个数组或vector存储优惠票，每次坐地铁的时候扫描一下。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

vector < pair < int , int > > vec;
const int MAXN = 1e5 + 5;
struct NODE {
    int ID;
    int Pri;
    int Tim;
} a[MAXN];
int n;
int ans;

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[i] = NODE{x, y, z};
        if (!a[i].ID) {
            ans += a[i].Pri;
            vec.push_back(make_pair(a[i].Pri, a[i].Tim));
            continue;
        }
        int Flag = false;
        for (int j = 0; j < vec.size(); ++j) {
            if (abs(a[i].Tim - vec[j].second) <= 45 && vec[j].first >= a[i].Pri) {
                vec.erase(vec.begin() + j);
                --j;
                Flag = true;
                break;
            }
            if (abs(a[i].Tim - vec[j].second) > 45)
                vec.erase(vec.begin() + j), --j;
        }
        if (!Flag) ans += a[i].Pri;
    }
    printf("%d\n", ans);
}

T3

完全背包的题

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <utility>
#define _ 0

using namespace std;

inline int read() {
    int a = 0, f = 1; char ch;
    while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
    while (isdigit(ch)) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = getchar();
    return a * f;
}

template<typename _T>
inline void write(_T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x /10);
    putchar(x % 10 + '0');
}

const int MAXN = 233333 + 5;
int T = read();
int n = read();
int m = read();
int o233[105][105];
int dp[MAXN];

signed main() {
    for (int i = 1; i <= T; ++i)
        for (int j = 1; j <= n; ++j)
            o233[i][j] = read();

    int ans = m;
    for (int i = 1; i <= T; ++i) {
        memset(dp, ~~(0^_^0), sizeof dp);
        dp[ans] = ans;
        for (int j = 1; j <= n; ++j)
            for (int k = ans; k >= o233[i][j]; --k)
                dp[k - o233[i][j]] = max(dp[k - o233[i][j]], dp[k] + o233[i + 1][j] - o233[i][j]);

        int maxNum = -2333333;
        for (int ljs = ~~(0^_^0); ljs <= ans; ++ljs)
            maxNum = max(maxNum, dp[ljs]);
        ans = maxNum;
    }
    write(ans);
    return 0;
}

T4

这道题还没有T3难

对这个图跑一遍Dijkstra或SPFA，（这次的数据不知道有没有卡SPFA）处理出所有点到原点的奇数最短路和偶数最短路。

因为边权一直为1，所以只需要用当前的奇数最短路更新偶数最短路，用当前的偶数最短路更新奇数最短路就行了。

有一个坑点在于，若源点是独立的，也就是说若1号结点没有出入度，那么这种情况是一直输出No

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <utility>

using namespace std;

inline int read() {
    int a = 0, f = 1; char ch;
    while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
    while (isdigit(ch)) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = getchar();
    return a * f;
}

template<typename _T>
inline void write(_T x) {
    if (x < 0) putchar('-'), x = -x;
    if (9 < x) write(x / 10);
    putchar(x % 10 + '0');
}

const int MAXN = 1e5 + 5;
struct UndirectedGraph {
    long long OddDis;
    long long EvenDis;
} dis[MAXN];
int head[MAXN << 1], _next[MAXN << 1];
int ver[MAXN << 1], edge[MAXN << 1];
int tot;
int n = read();
int m = read();
int q = read();

inline void addEdge(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z;
    _next[tot] = head[x], head[x] = tot;
}

inline void SPFA() {
    for (int i = 1; i <= n; ++i)
        dis[i].EvenDis = dis[i].OddDis = 0x7fffffff;
    queue<int> Q;
    Q.push(1);
    dis[1].EvenDis = 0;
    while (Q.size()) {
        int x = Q.front(); Q.pop();
        for (int i = head[x]; i; i = _next[i]) {
            int y = ver[i];
            int z = edge[i];
            int OddDis = dis[y].OddDis;
            int EvenDis = dis[y].EvenDis;
            dis[y].OddDis = min(dis[y].OddDis, dis[x].EvenDis + z);
            dis[y].EvenDis = min(dis[y].EvenDis, dis[x].OddDis + z);
            if (dis[y].EvenDis ^ EvenDis || dis[y].OddDis ^ OddDis)
                Q.push(y);
        }
    }
}

signed main() {
    bool flag = false;
    for (int i = 1; i <= m; ++i) {
        int from = read();
        int to = read();
        addEdge(from, to, 1);
        addEdge(to, from, 1);
        if (from == true || to == true) flag = 1;
    }
    SPFA();
    for (int i = 1; i <= q; ++i) {
        int ID = read();
        int wanted = read();
        if (ID == 1 && !flag) {
            puts("No");
            continue;
        }
        if (dis[ID].OddDis == 0x7fffffff && dis[ID].EvenDis == 0x7fffffff) {
            puts("No");
            continue;
        }
        if (((wanted & 1) && dis[ID].OddDis <= wanted) || ((~wanted & 1) && dis[ID].EvenDis <= wanted)) puts("Yes");
        else puts("No");
    }
    #define _ 0
    return ~~(0^_^0);
}

Luogu

楔子

一道板子题

题意：求两个大整数相乘的积.

选手1：我会$\mathsf{unsigned\ long\ long}$！

预计得分：$0\mathsf{pts}$

选手2：我会高精！

预计得分：$30\mathsf{pts}$

选手3：我会$\mathsf{Python}$！

预计得分：$\cdots$

(选手3被众人围殴致死)

卷积思想

引入 1

求两个无符号整数相乘的积.

在这里，我们并不是想编写一个程序来实现上述功能，而是老老实实用纸笔计算.

例：

计算 $21\times121$

解： $$\quad\ \ 21$$ $$\times\ 121$$

$$\quad\ \ 21$$ $$\ 42$$ $$\!\!\!\!21$$

$$\!2541$$

答：$21\times121=2541.$

回顾刚才的计算过程，我们分析一下$2541$的每一位数字是怎么得出来的.

$1=1\times1$

$4=2\times1+2\times2$

$5=2\times2+1\times1$

$2=2\times1$

我们用数组$A$存储$21$这个数，$B$存储$121$，$C$存储答案，则

$C_0=A_0\times B_0$

$C_1=A_1\times B_0+A_0\times B_1$

$C_2=A_1\times B_1+A_0\times B_2$

$C_3=A_1\times B_2$

观察下标，我们发现两个正整数相乘的结果满足下面规律：

$$ C_k=\sum^k_{i=0}A_i\times B_{k-i} $$

引入 2

求两个多项式相乘的积.

同上例，我们依然用纸笔计算之.

例：

计算$(1+2x)(1+2x+x^2)$

解：

$(1+2x)(1+2x+x^2)=1+2x+x^2+2x+4x^2+2x^3=1+4x+5x^2+2x^3$

根据计算过程分析各项系数，有：

$1=1\times1$

$4=2\times1+2\times2$

$5=2\times2+1\times1$

$2=2\times1$

这里我们用数组$A$存储$(1+2x)$的系数，$B$存储$(1+2x+x^2)$的系数，$C$存储答案的系数，则：

$C_0=A_0\times B_0$

$C_1=A_1\times B_0+A_0\times B_1$

$C_2=A_1\times B_1+A_0\times B_2$

$C_3=A_1\times B_2$

我们发现，两个多项式乘积的系数满足下面的规律：

$$ C_k=\sum^k_{i=0}A_i\times B_{k-i} $$

卷积？！

我们观察上面两个式子，可以看出它们具有相同的形式，我们称这种形式为卷积.

形象理解：

“卷积”，“积”自然指乘积，而“卷”的含义如图：

第一次尝试

#include<cmath>
#include<cstdio>
const int N = 1000005, mod = 998244353;
int A[N], B[N], C[N];
int a, b;
void mutiply()
{
    for(int k = 0; k < a + b - 1; ++k)
        for(int i = 0; i <= k; ++i)
            C[k] += (A[i]*B[k-i]);
}
int main()
{
    scanf("%d%d",&a,&b);
    ++a,++b;
    for(int i=0;i<a;++i)scanf("%d",A+i);
    for(int i=0;i<b;++i)scanf("%d",B+i);
    mutiply();
    for(int i=0;i<a+b-1;++i)printf("%d ",C[i]);
    return 0;
}

干得漂亮！我们收获了$44\mathsf{pts}$的佳绩！

另一种方法

之前有用到这样一个思路，对于任意多项式$F$，我们可以采用将其升幂排列，再存储其系数的办法来表示出$F$.

这里谈谈另外一种办法.

众所周知，两点确定一条直线，用解析几何的语言描述，就是 $y=ax+b$由两个有序点对${(x_0,y_0),(x_1,y_1)}$唯一地确定.

为什么？因为我们知道了这两个点的坐标，将其带入进解析式，得到二元一次方程组，再解这个方程组，得到$a$和$b$的值.

当$y=ax^2+bx+c$时呢？进一步地，当$y=a_0x^0+a_1x^1+\cdots+a_nx^n$时呢？

我们可以看出，式子$y=a_0x^0+a_1x^1+\cdots+a_nx^n$有$(n+1)$个系数，如果我们要唯一地确定它，就需要$(n+1)$个点的坐标联立起来解出系数.

也就是说，$(n+1)$个有序点对可以唯一表示一个多项式，我们称其为“点值表示法”

但是

它有什么用？我们知道，将两个浮点数相乘的时间复杂度是$O(1)$的，那么，假设我们有两个多项式$A$和$B$，不妨设它们为$(1+2x)$和$(1+2x+x^2)$，接下来，我们计算它们在一些点上的值： $$ x\quad A\quad B $$ $$ 0\quad\ 1\quad\ 1 $$ $$ 1\quad\ 3\quad\ 4 $$ $$ 2\quad\ 5\quad\ 9 $$ $$ 3\quad7\quad16 $$ $$ 4\quad9\quad25 $$ 将$A$列和$B$列对应的数相乘，记作$C$列，则 $$ x\quad C $$ $$ 0\quad\ 1 $$ $$ 1\quad12 $$ $$ 2\quad45 $$ $$ 3\ \ 112 $$ $$ 4\ \ 225 $$ 在上面我们求得$A\times B$，我们将$x={0,1,2,3,4}$代入$A\times B$， $$ x\quad A\times B $$ $$ 0\quad\quad\quad\ 1 $$ $$ 1\quad\quad\quad12 $$ $$ 2\quad\quad\quad45 $$ $$ 3\quad\quad\ \ 112 $$ $$ 4\quad\quad\ \ 225 $$

相等？！

是的，当我们转换为点值表示法时，两个多项式在某点上的值的乘积等于两个多项式的乘积在某点上的值.(显然$F(x)\times G(x)=F(x)\times G(x)$，等号左边是点值表示法的$F$和$G$在$x$处的值的乘积，等号右边是它们的乘积在$x$处的值，慢慢品味.)

设这两个多项式是$m$和$n$次的，则它们的乘积是$(m+n)$次的，所以，我们只要计算这两个多项式在$(m+n+1)$个点上的值并一一相乘，就可以确定这两个多项式的乘积.

时间复杂度？$O(n+m)\qquad\mathsf{Good\ Job!}$

且慢

$1)$如何将点值表示法转换为系数表示法？

$2)$我们该如何选取那些待计算的点？显然，我们需要在这些点上计算它的平方，立方甚至更高次方，而且，如果我们能合理地选择待计算的点，那么计算将会极大地简化.

接下来我们将会看到一类名叫单位根的复数，结合分治思想后可以将时间复杂度降低到$O(n\log n)$.

但首先，我们还是要了解$\cdots$

复数

复数是形如$a+bi$的数，其中$a,b\in\mathrm{R},i=\sqrt{-1}$.

将全体复数的集合称作$\mathrm{C}$

复数的三则运算（除法现在还用不到）

• $(a+bi)+(c+di)=(a+b)+(c+d)i$
• $(a+bi)-(c+di)=(a-b)+(c-d)i$
• $(a+bi)\times(c+di)=(ac-bd)+(bc+ad)i$

证明：注意$i^2=-1$，利用结合律，分配律即证.

注：复数也满足结合律，分配律和幂运算规则.

欧拉公式和单位根

欧拉公式：$e^{i\theta}=\cos\theta+i\sin\theta$

注意到$e^{(2a+1)\pi i}=-1,e^{2a\pi i}=1,a\in\mathrm{N}$

则方程$x^n=1$的根（称作单位根，记作$\omega^k_n$)为 $$ \omega^k_n=e^{\frac{2k\pi}{n}i}=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n} $$ 证明：由$(a^x)^p=a^{xp}$结合欧拉公式即证得其为方程的根.

单位根的性质

$1)\omega^k_n=\omega^{k\%n}_n$

证：$\omega^k_n=\cos\dfrac{2k\pi}{n}+i\sin\dfrac{2k\pi}{n}=\cos\dfrac{2(k\%n)\pi}{n}+i\sin\dfrac{2(k\%n)\pi}{n}=\omega^{k\%n}_n$

其中倒数第二步是当$k\ge n$时，将$k$约去得到$k\%n$.

$2)\omega^k_n=(\omega^1_n)^k$

证：$\omega^k_n=e^{\frac{2k\pi}{n}i}=e^{\frac{2\pi}{n}i\times k}=(e^{\frac{2\pi}{n}i})^k=(\omega^1_n)^k$

$3)\omega^0_n=1$

证：$\omega^0_n=\cos0+i\sin0=1+0i=1$

$4)\omega^k_n\times \omega^j_n=\omega^{k+j}_n$

证：$\omega^k_n\times \omega^j_n=(\omega^1_n)^k\times(\omega^1_n)^j=(\omega^1_n)^{k+j}=\omega^{k+j}_n$

$5)\omega^{pk}_{pn}=\omega^k_n$

证：$\omega^{pk}_{pn}=e^{\frac{2pk\pi}{pn}i}=e^{\frac{2k\pi}{n}i}=\omega^k_n$

$6)\omega^{k+\frac{n}{2}}_n=-\omega^k_n$

证：$\omega^{k+\frac{n}{2}}_n=\omega^{\frac{2k+n}{2}}_n=e^{\frac{(2k+n)\pi}{n}i}=e^{\frac{2k\pi}{n}i+\pi i}=e^{\frac{2k\pi}{n}i}\times e^{\pi i}=-e^{\frac{2k\pi}{n}i}=-\omega^k_n$

回到多项式

关于复数和单位根的性质已经说得够多了，现在把注意力放到多项式中.

前面有提到分治思想，现在我们来好好研究一下.

设多项式$F(x)=a_0x^0+a_1x^1+\cdots+a_{n-1}x^{n-1}=\sum^{n-1}_{i=0}a_ix^i$，则它可以唯一地表示成两个多项式的和.哪两个？请看： $$ F(x)=\sum^{n-1}_{i=0}a_ix^i=\sum^{\frac{n}{2}-1}_{i=0}a_{2i}x^{2i}+\sum^{\frac{n}{2}-1}_{i=0}a_{2i+1}x^{2i+1} $$ 即：按照次数的奇偶性将多项式$F$分成$L,R$两个部分.

那么，为什么要这么分？请继续向下看.

记 $$ L(x)=\sum^{\frac{n}{2}-1}_{i=0}a_{2i}x^{i} $$ $$ R(x)=\sum^{\frac{n}{2}-1}_{i=0}a_{2i+1}x^{i} $$ 则 $$ F(x)=\sum^{\frac{n}{2}-1}_{i=0}a_{2i}x^{2i}+\sum^{\frac{n}{2}-1}_{i=0}a_{2i+1}x^{2i+1}=\sum^{\frac{n}{2}-1}_{i=0}a_{2i}(x^2)^i+\sum^{\frac{n}{2}-1}_{i=0}a_{2i+1}(x^2)^i\times x=L(x^2)+xR(x^2) $$

重头戏

这里$F$是$(n-1)$次的多项式，需要$n$个点来确定.

将单位根$\omega^k_n$代入 $$ F(x)=L(x^2)+xR(x^2) $$ 得 $$ F(\omega^k_n)=L(\omega^{2k}_n)+\omega^k_nR(\omega^{2k}_n) $$ 即 $$ (1):\qquad F(\omega^k_n)=L(\omega^{k}_{\frac{n}{2}})+\omega^k_nR(\omega^{k}_{\frac{n}{2}}) $$ 则我们得到了$F(x)$在$\omega^0_n,\omega^1_n,\cdots,\omega^{\frac n2-1}_n$这$\dfrac n2$个点上的值.

那另外$\dfrac n2$点上的值呢？

将单位根$\omega^{k+\frac n2}_n$代入 $$ F(x)=L(x^2)+xR(x^2) $$ 得 $$ F(\omega^k_n)=L(\omega^{2k+n}_n)+\omega^{k+\frac n2}_nR(\omega^{2k+n}_n) $$ 即 $$ F(\omega^k_n)=L(\omega^{2k}_n)+\omega^{k+\frac n2}_nR(\omega^{2k}_n) $$ 即 $$ (2):\qquad F(\omega^k_n)=L(\omega^{k}_{\frac{n}{2}})-\omega^k_nR(\omega^{k}_{\frac{n}{2}}) $$ 则我们得到了$F(x)$在$\omega^{\frac n2}_n,\omega^{\frac n2+1}_n,\cdots,\omega^{n-1}_n$这另外$\dfrac n2$个点上的值.

对比$(1)$和$(2)$，可以看出它们之间只差了一个正负号.

所以只要知道$L$和$R$在$\omega^0_{\frac n2},\omega^1_{\frac n2},\cdots,\omega^{\frac n2-1}_{\frac n2}$的值，就可以在$O(n)$的时间复杂度内唯一地确定$F$.

那么，如何求得$L$和$R$在这些点上的值呢？

注意到：$L$和$R$都是$\dfrac n2$项的多项式！

分治

所以，我们将规模为$n$的多项式求值问题分解成了规模为$\dfrac n2$的子问题！

递归地求解即可.

一个小细节：为了避免出现$2\nmid n$的情况，我们强行向高位补零，补成一个具有$2^k$项的多项式.

综合运用

这就是$\mathsf{DFT}$：离散傅里叶变换！

代码实现：

void dft(comp *f,int len)
{
    if(len==1)return ;
    comp *fL=f,*fR=f+len/2;
    for(int k=0;k<len;k++)G[k]=f[k];
    for(int k=0;k<len/2;k++)L[k]=G[k<<1],R[k]=G[k<<1|1];
    dft(L,len/2);
    dft(R,len/2);
    comp W(cos(2*pi/len),sin(2*pi/len)),b(1,0);
    for(int k=0;k<len/2;k++)
    {
        G[k]=L[k]+b*R[k];
        G[k+len/2]=L[k]-b*R[k];
        b*=W;
    }
    for(int k=0;k<len;k++)f[k]=G[k];
}

反过来

设$G(z)=\mathcal{F}[F(x)]$，则$F(x)=\mathcal F^{-1}[G(z)]$.

其中$\mathcal F$称作（离散）傅里叶变换，$\mathcal F^{-1}$称作（离散）逆傅里叶变换，又称$\mathsf{IDFT}$.

$\mathsf{I}:\mathsf{Inversed}$

IDFT原理

结论：

（$f_i,g_i$为$F,G$第$i$项的系数）

$$ nf_k=\sum^{n-1}_{i=0}\omega^{-ki}_ng_i $$

负数次单位根？

由定义知$\omega^{-k}_n=(\omega^{-1}_n)^k$

那么$\omega^{-1}_n=\cos-\dfrac{2\pi}{n}+i\sin-\dfrac{2\pi}{n}=\cos\dfrac{2\pi}{n}-i\sin\dfrac{2\pi}{n}$

证明？诱导公式！

优化

将递归转换为循环，避免数组的拷贝，我们可以写出以下代码，这就是经典的快速傅里叶变换！

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 5100000, mod = 998244353;
const double pi=acos(-1);
int n,m;
struct comp
{
    comp (double _a=0,double _b=0){a=_a,b=_b;}
    double a,b;
    comp operator + (comp const &B) const
    {return comp(a+B.a,b+B.b);}
    comp operator - (comp const &B) const
    {return comp(a-B.a,b-B.b);}
    comp operator * (comp const &B) const
    {return comp(a*B.a-b*B.b,a*B.b+b*B.a);}
}F[N],G[N];
int t[N];
void fft(comp *f,bool flag)
{
    for (int i=0;i<n;i++)
    if (i<t[i])swap(f[i],f[t[i]]);
    for(int p=2;p<=n;p<<=1)
    {
    int len=p>>1;
    comp W(cos(2*pi/p),sin(2*pi/p));
    if(!flag)W.b*=-1;
    for(int k=0;k<n;k+=p)
         {
        comp b(1,0);
        for(int l=k;l<k+len;l++)
        {
            comp temp=b*f[len+l];
            f[len+l]=f[l]-temp;
            f[l]=f[l]+temp;
            b=b*W;
        }
    }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n;i++)scanf("%lf",&F[i].a);
    for (int i=0;i<=m;i++)scanf("%lf",&F[i].b);
    for(m+=n,n=1;n<=m;n<<=1);
    for(int i=0;i<n;i++)t[i]=(t[i>>1]>>1)|((i&1)?n>>1:0);
    fft(F,1);
    for(int i=0;i<n;++i)F[i]=F[i]*F[i];
    fft(F,0);
    for(int i=0;i<=m;++i)printf("%d ",(int)(F[i].b/n/2+0.49));
    return 0;
}

三次变两次优化

上面的代码中有体现

设 $P=F+iG$

则 $P^2=F^2-G^2+2iFG$

即，将输入当作一个多项式的实部和虚部，将其$\mathsf{FFT}$后自乘，再$\mathsf{IFFT}$回来，输出就是虚部除以$2$

最终尝试

$\mathtt{Accepted!}$

习题和拓展阅读

#6393

快速数论变换

$$ \mathrm{END.} $$

欧拉公式:

$$ \mathrm{e}^{i\theta}=\cos\theta+i\sin\theta $$

关于 $\omega$

$$ \omega^3=1,\omega+1=-\omega^2,\omega^2+1=-\omega $$

e.g.1:

分解因式: $ x^5\! -1 $

解}:

$$\cos\frac{2\pi}{5}+i\sin\frac{2\pi}{5},\cos\frac{4\pi}{5}+i\sin\frac{4\pi}{5}$$

$$\cos\frac{6\pi}{5}+i\sin\frac{6\pi}{5},\cos\frac{8\pi}{5}+i\sin\frac{8\pi}{5},1$$

由 $$f(x)=a_nx^n+a_{n-1}+x^{x-1}+\cdots+a_1x+a_0$$

可得: $$x^5-1$$

$$=(x-1)(x-\cos\frac{2\pi}{5}-i\sin\frac{2\pi}{5})(x-\cos\frac{4\pi}{5}-i\sin\frac{4\pi}{5})(x-\cos\frac{6\pi}{5}-i\sin\frac{6\pi}{5})(x-\cos\frac{8\pi}{5}-i\sin\frac{8\pi}{5})$$

因为 $$ \cos\frac{8\pi}5+i\sin\frac{8\pi}5=\cos\frac{2\pi}5-i\sin\frac{2\pi}5, $$

与 $$ \cos\frac{2\pi}5+i\sin\frac{2\pi}5 $$ 共轭,又

$$ \cos\frac{6\pi}5+i\sin\frac{6\pi}5=\cos\frac{4\pi}5-i\sin\frac{4\pi}5, $$

与

$$ \cos\frac{4\pi}5+i\sin\frac{4\pi}5 $$

共轭，并且:

$$ \sin^2\alpha+\cos^2\alpha=1 $$

所以:

$$ (x-\cos\frac{2\pi}5-i\sin\frac{2\pi}5)(x-\cos\frac{2\pi}5 +i\sin\frac{2\pi}5) $$

$ \ \ \ \ \ \ \ \ =(x-\cos\frac{2\pi}5)^2+(\sin\frac{2\pi}5)^2 $

$ \ \ \ \ \ \ \ \ =x^2-(2\cos\frac{2\pi}5)x+1,(x-\cos\frac{4\pi}5-i\sin\frac{4\pi}5)(x-\cos\frac{4\pi}5+i\sin\frac{4\pi}{5}) $

$ \ \ \ \ \ \ \ \ =x^2-(2\cos\frac{4\pi}5)x+1 $

所以，在实数集内，可得:

$$x^5-1$$

$$=(x-1)[x^2-(2\cos\frac{2\pi}5)x+1][x^2-(2\cos\frac{4\pi}5)x+1]$$

在有理数集内，可得:

$$x^5-1$$

$$=(x-1)(x^4+x^3+x^2+x+1)$$

$(x^4+x^3+x^2+x+1)$

因为 $(x^4+x^3+x^2+x+1)$ 是分圆多项式

所以 $(x^4+x^3+x^2+x+1)$ 在有理数集内是既约多项式

关于$\omega_n^k$

$$ {\omega^k_n=\cos\frac{2kn}{n}}+i\sin\frac{2k\pi}{n}(k=1,2,\cdots,n)=e^{\frac{2k\pi}{n}i} $$

$1)\omega^k_n=\omega^{k\%n}_n$

证：$\omega^k_n=\cos\dfrac{2k\pi}{n}+i\sin\dfrac{2k\pi}{n}=\cos\dfrac{2(k\%n)\pi}{n}+i\sin\dfrac{2(k\%n)\pi}{n}=\omega^{k\%n}_n$

其中倒数第二步是当$k\ge n$时，将$k$约去得到$k\%n$.

$2)\omega^k_n=(\omega^1_n)^k$

证：$\omega^k_n=e^{\frac{2k\pi}{n}i}=e^{\frac{2\pi}{n}i\times k}=(e^{\frac{2\pi}{n}i})^k=(\omega^1_n)^k$

$3)\omega^0_n=1$

证：$\omega^0_n=\cos0+i\sin0=1+0i=1$

$4)\omega^k_n\times \omega^j_n=\omega^{k+j}_n$

证：$\omega^k_n\times \omega^j_n=(\omega^1_n)^k\times(\omega^1_n)^j=(\omega^1_n)^{k+j}=\omega^{k+j}_n$

$5)\omega^{pk}_{pn}=\omega^k_n$

证：$\omega^{pk}_{pn}=e^{\frac{2pk\pi}{pn}i}=e^{\frac{2k\pi}{n}i}=\omega^k_n$

$6)\omega^{k+\frac{n}{2}}_n=-\omega^k_n$

证：$\omega^{k+\frac{n}{2}}_n=\omega^{\frac{2k+n}{2}}_n=e^{\frac{(2k+n)\pi}{n}i}=e^{\frac{2k\pi}{n}i+\pi i}=e^{\frac{2k\pi}{n}i}\times e^{\pi i}=-e^{\frac{2k\pi}{n}i}=-\omega^k_n$

以上来自李琰，经我检验，没锅。

排列和组合数证明

$$A_n^k=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}(k\le n),0!=1$$

证明

看到好像没有splay的题解，来补一波~~

找到1-x的区间，然后转到后面，在删除第一个就好了

需吸氧

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <cctype>
#define mid (l + r >> 1)

using namespace std;

const int SIZE = 7e5 + 5;
struct SPLAY {
    int siz;
    int val;
    int ch[2];
    int fa;
} T[SIZE];
int root, n, R[SIZE], tot;

inline void update(int u) {
    T[u].siz = T[T[u].ch[0]].siz + T[T[u].ch[1]].siz + 1;
}

inline int make(int l, int r, int fa) {
    int u = ++tot;
    T[u].siz = 1;
    T[u].val = mid;
    T[u].ch[0] = T[u].ch[1] = 0;
    T[u].fa = fa;
    if (mid > l) T[u].ch[0] = make(l, mid - 1, u);
    if (mid < r) T[u].ch[1] = make(mid + 1, r, u);
    update(u);
    return u;
}

inline void rotate(int x) {
    int y = T[x].fa;
    int z = T[y].fa;
    int w = T[y].ch[1] == x;
    T[z].ch[T[z].ch[1] == y] = x;
    T[x].fa = z;
    T[y].ch[w] = T[x].ch[w ^ 1];
    T[T[x].ch[w ^ 1]].fa = y;
    T[x].ch[w ^ 1] = y;
    T[y].fa = x;
    update(y), update(x);
}

inline void splay(int x, int goal) {
    for (; T[x].fa ^ goal; rotate(x)) {
        int y = T[x].fa;
        int z = T[y].fa;
        if (z ^ goal)
            T[y].ch[1] ^ x ^ T[z].ch[1] ^ y ? rotate(x) : rotate(y);
    }
    if (!goal) root = x;
}

inline int getRank(int x) {
    int u = root;
    while (233) {
        if (x <= T[T[u].ch[0]].siz) u = T[u].ch[0];
        else {
            x -= T[T[u].ch[0]].siz + 1;
            if (!x) return u;
            u = T[u].ch[1];
        }
    }
}

inline int getcard(int x) {
    if (x) {
        splay(getRank(x), 0);
        int u = root;
        root = T[u].ch[1];
        T[root].fa = 0;
        T[u].ch[1] = 0;
        update(u);
        splay(getRank(T[root].siz), 0);
        if (u) T[u].fa = root;
        if (root) T[root].ch[1] = u, update(root);
    }
    int ranker = getRank(1);
    int res = T[ranker].val;
    splay(ranker, 0);
    if (T[ranker].ch[1])
        T[root = T[ranker].ch[1]].fa = 0;
    return res;
}

signed main() {
    scanf("%d", &n);
    root = make(1, n, 0);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &R[i]);
        printf("%d\n", getcard(R[i] % T[root].siz));
    }
    return 0;
}