BZOJ2194 快速傅立叶之二 < FFT >

Problem

快速傅立叶之二

Description

请计算其中，并且有。
中的元素均为小于等于的非负整数。

Input

第一行一个整数，接下来行，每行两个数，依次表示。

Output

输出行，每行一个整数，第行输出。

Sample Input

5
3 1
2 4
1 1
2 4
1 4

Sample Output

24
12
10
6
1

标签：FFT

Solution

裸题。

将的下标变为负值做即可，变为负值可以直接将数组整体右移。

Code

#include <bits/stdc++.h>
#define MOD 9999991
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;	lnt ans = 1;
int main() {
    read(n);
    for (int i = 1; i <= n-2; i++) (ans *= 1LL*n) %= MOD; 
    for (int i = 1; i <= n-1; i++) (ans *= 1LL*i) %= MOD;
    return printf("%lld\n", ans), 0;
}