2017.8.17 ACM 训练赛 参考

ultmaster edited 7 年,2 月前

卷积

你可以用 FFT(快速傅里叶变换)在 $O(n \log n)$ 的时间内计算两个多项式的乘积。如果要模比较特殊的素数,例如 $998~244~353$,可以使用 NTT。具体实现细节不作要求,这里给出 API。

例如对两个 $n$ 阶多项式 $(a_0+a_1 x+a_2 x^2 + \cdots + a_n x^n)(b_0+b_1 x+b_2 x^2 + \cdots + b_n x^n)$ 的乘积,我们可以调用 solve 函数(请确保 a, b 数组足够大,因为展开结果可能更大,一般建议开到四倍以上)。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int G = 3;

int quick_pow(int a, int b) {
    if (b == 0) return 1;
    if (b == 1) return a % MOD;
    int res = quick_pow(a, b / 2);
    res = 1LL * res * res % MOD;
    if (b & 1) res = 1LL * res * a % MOD;
    return res;
}

void ntt(int * a, int N, int f) {
    int i, j = 0, t, k;
    for (i = 1; i < N - 1; i++) {
        for (t = N; j ^= t >>= 1, ~j & t;);
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    for (i = 1; i < N; i <<= 1) {
        t = i << 1;
        int wn = quick_pow(G, (MOD - 1) / t);
        for (j = 0; j < N; j += t) {
            int w = 1;
            for (k = 0; k < i; k++, w = 1LL * w * wn % MOD) {
                int x = a[j + k], y = 1LL * w * a[j + k + i] % MOD;
                a[j + k] = (x + y) % MOD, a[j + k + i] = (x - y + MOD) % MOD;
            }
        }
    }
    if (f == -1) {
        reverse(a + 1, a + N);
        int inv = quick_pow(N, MOD - 2);
        for (i = 0; i < N; i++)
            a[i] = 1LL * a[i] * inv % MOD;
    }
}

int* solve(int* a, int *b, int n) {
    int N = 1;
    while (N <= 2 * n)
        N <<= 1;
    ntt(a, N, 1);
    ntt(b, N, 1);
    for (int i = 0; i < N; ++i)
        a[i] = 1LL * a[i] * b[i] % MOD;
    ntt(a, N, -1);
    return a;
}

int main() {
    int a[16] = {1, 2, 1};
    int b[16] = {3, 4, 1};
    solve(a, b, 2);
    for (int i = 0; i < 16; ++i) {
        printf("%d\n", a[i]);
    }
    // now a[] = {3, 10, 12, 6, 1};
}

日期处理魔法

// Routines for performing computations on dates.  In these routines,
// months are exprsesed as integers from 1 to 12, days are expressed
// as integers from 1 to 31, and years are expressed as 4-digit
// integers.

string dayOfWeek[] = {"Mo", "Tu", "We", "Th", "Fr", "Sa", "Su"};

// converts Gregorian date to integer (Julian day number)

int DateToInt (int m, int d, int y){  
  return 
    1461 * (y + 4800 + (m - 14) / 12) / 4 +
    367 * (m - 2 - (m - 14) / 12 * 12) / 12 - 
    3 * ((y + 4900 + (m - 14) / 12) / 100) / 4 + 
    d - 32075;
}

// converts integer (Julian day number) to Gregorian date: month/day/year

void IntToDate (int jd, int &m, int &d, int &y){
  int x, n, i, j;

  x = jd + 68569;
  n = 4 * x / 146097;
  x -= (146097 * n + 3) / 4;
  i = (4000 * (x + 1)) / 1461001;
  x -= 1461 * i / 4 - 31;
  j = 80 * x / 2447;
  d = x - 2447 * j / 80;
  x = j / 11;
  m = j + 2 - 12 * x;
  y = 100 * (n - 49) + i + x;
}

// converts integer (Julian day number) to day of week

string IntToDay (int jd){
  return dayOfWeek[jd % 7];
}

Comments