2017.8.17 ACM 训练赛 参考

ultmaster edited 2 年，5 月前

卷积

#include &lt;bits/stdc++.h&gt;
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 &amp; 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 &lt; N - 1; i++) {
for (t = N; j ^= t &gt;&gt;= 1, ~j &amp; t;);
if (i &lt; j) {
swap(a[i], a[j]);
}
}
for (i = 1; i &lt; N; i &lt;&lt;= 1) {
t = i &lt;&lt; 1;
int wn = quick_pow(G, (MOD - 1) / t);
for (j = 0; j &lt; N; j += t) {
int w = 1;
for (k = 0; k &lt; 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 &lt; N; i++)
a[i] = 1LL * a[i] * inv % MOD;
}
}

int* solve(int* a, int *b, int n) {
int N = 1;
while (N &lt;= 2 * n)
N &lt;&lt;= 1;
ntt(a, N, 1);
ntt(b, N, 1);
for (int i = 0; i &lt; 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 &lt; 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 &amp;m, int &amp;d, int &amp;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];
}