T1 Matrix
很容易想到一个 \(O(n^4)\) 做法，用 uint128 压位，然后你发现它过了……
正解考虑分治，取出矩阵中间的列 \(mid\) ，由于跨越 \(mid\) 列的询问必然经过 \(mid\) 列上一点，因此对于 \(mid\) 左边的点，预处理每个点向右，向下可以到达的所有 \(mid\) 处的点，对于 \(mid\) 右边的点，预处理每个点向左，向上可以到达的所有 \(mid\) 处的点，使用 bitset 可以做到 \(O(\tfrac{n^3}{w})\) 预处理，之后对于每个跨过 \(mid\) 的询问，可以在 \(O(\tfrac{n}{q})\) 的复杂度下进行查询，总复杂度可以做到 \(O(\tfrac{n^2m\log m+nq}{w})\) 。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
const int max1 = 500, max2 = 1e6;
int n, m, q;
char s[max1 + 5][max1 + 5];
struct Question
{
int id, A, B, C, D;
Question () {}
Question ( int __id, int __A, int __B, int __C, int __D )
{ id = __id, A = __A, B = __B, C = __C, D = __D; }
};
vector <Question> qus[max1 + 5];
void Insert ( int L, int R, const Question &Q )
{
int mid = L + R >> 1;
if ( Q.C <= mid && Q.D >= mid )
return qus[mid].push_back(Q);
if ( Q.D < mid )
Insert(L, mid - 1, Q);
else
Insert(mid + 1, R, Q);
return;
}
bitset <max1 + 5> bit[max1 + 5][max1 + 5];
bitset <max2 + 5> ans;
void Solve ( int L, int R )
{
if ( L > R )
return;
int mid = L + R >> 1;
if ( !qus[mid].empty() )
{
for ( int i = 1; i <= n; i ++ )
{
bit[i][mid].reset();
if ( s[i][mid] == '0' )
bit[i][mid][i] = 1;
}
for ( int i = n; i >= 1; i -- )
{
for ( int j = mid - 1; j >= L; j -- )
{
if ( s[i][j] == '0' )
{
bit[i][j] = bit[i][j + 1];
if ( i < n && s[i + 1][j] == '0' )
bit[i][j] |= bit[i + 1][j];
}
else
bit[i][j].reset();
}
}
for ( int i = 1; i <= n; i ++ )
{
if ( i > 1 && s[i][mid] == '0' )
bit[i][mid] |= bit[i - 1][mid];
for ( int j = mid + 1; j <= R; j ++ )
{
if ( s[i][j] == '0' )
{
bit[i][j] = bit[i][j - 1];
if ( i > 1 && s[i - 1][j] == '0' )
bit[i][j] |= bit[i - 1][j];
}
else
bit[i][j].reset();
}
}
for ( auto Q : qus[mid] )
{
if ( Q.C == mid )
ans[Q.id] = bit[Q.B][Q.D][Q.A];
else
ans[Q.id] = ( bit[Q.A][Q.C] & bit[Q.B][Q.D] ).any();
}
}
Solve(L, mid - 1);
Solve(mid + 1, R);
return;
}
int main ()
{
freopen("matrix.in", "r", stdin);
freopen("matrix.out", "w", stdout);
scanf("%d%d%d", &n, &m, &q);
for ( int i = 1; i <= n; i ++ )
scanf("%s", s[i] + 1);
for ( int i = 1, A, B, C, D; i <= q; i ++ )
{
scanf("%d%d%d%d", &A, &B, &C, &D);
Insert(1, m, Question(i, A, B, C, D));
}
Solve(1, m);
for ( int i = 1; i <= q; i ++ )
{
if ( ans[i] )
puts("Yes");
else
puts("No");
}
return 0;
}
T2 Travel
考虑枚举环的起点依次处理每个询问，断裂环上所有跨过起点的边（包括从起点出发和从起点结束的边），容易发现左右两边构成一些链，设左边链的条数为 \(x\) ，显然右边链的条数只能为 \(x,x+1,x-1\) ，假设当前我们知道左边和右边链的方案数为 \(A,B\) ，考虑进行合并，如果左右两边链的条数均为 \(x\) ，由于两侧的链存在顺序关系，显然有贡献 \((x!)^2\) ，由于从起点出发的边可以选择左右两个方向，因此有贡献 \(2\) ，如果左右两边链的条数为 \(x,x+1\) ，同样有贡献 \(x!(x+1)!\) ，此时从起点出发的边只能选择链的条数较多的方向，因此贡献为 \(1\) ，左右两边链的条数为 \(x,x-1\) 同理。
因此考虑 dp 左右两边链的方案数，设 \(f_{i,j}\) 表示从左向右考虑到第 \(i\) 个点，此时有 \(j\) 条链的方案数，转移只需要考虑新开一条链，将点连接在链头，将点连接到链尾，拼接两条链进行转移即可，需要注意的是，从左向右 dp 时需要保证链尾方向向右，同理从右向左 dp 时需要保证链尾方向向左。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int max1 = 5000;
const int mod = 1e9 + 7;
int n; char s[max1 + 5];
int f[max1 + 5][max1 + 5], g[max1 + 5][max1 + 5], fac[max1 + 5];
void Add ( int &x, int y )
{
x += y;
if ( x >= mod )
x -= mod;
return;
}
int main ()
{
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
scanf("%s", s + 1); n = strlen(s + 1);
f[0][0] = 1;
for ( int i = 0; i <= n - 1; i ++ )
{
for ( int j = 0; j <= i; j ++ )
{
if ( !f[i][j] )
continue;
if ( s[i + 1] == '>' )
{
Add(f[i + 1][j], 1LL * f[i][j] * j % mod);
Add(f[i + 1][j + 1], f[i][j]);
}
else
{
Add(f[i + 1][j], 1LL * f[i][j] * j % mod);
if ( j > 1 )
Add(f[i + 1][j - 1], 1LL * f[i][j] * j % mod * ( j - 1 ) % mod);
}
}
}
g[n + 1][0] = 1;
for ( int i = n + 1; i >= 2; i -- )
{
for ( int j = 0; j <= n + 1 - i; j ++ )
{
if ( !g[i][j] )
continue;
if ( s[i - 1] == '<' )
{
Add(g[i - 1][j], 1LL * g[i][j] * j % mod);
Add(g[i - 1][j + 1], g[i][j]);
}
else
{
Add(g[i - 1][j], 1LL * g[i][j] * j % mod);
if ( j > 1 )
Add(g[i - 1][j - 1], 1LL * g[i][j] * j % mod * ( j - 1 ) % mod);
}
}
}
fac[0] = 1;
for ( int i = 1; i <= n; i ++ )
fac[i] = 1LL * fac[i - 1] * i % mod;
for ( int i = 1; i <= n; i ++ )
{
int ans = 0;
for ( int k = 0; k <= min(i - 1, n - i); k ++ )
{
Add(ans, 1LL * f[i - 1][k] * g[i + 1][k] % mod * fac[k] % mod * fac[k] % mod * 2 % mod);
Add(ans, 1LL * f[i - 1][k] * g[i + 1][k + 1] % mod * fac[k] % mod * fac[k + 1] % mod);
Add(ans, 1LL * f[i - 1][k + 1] * g[i + 1][k] % mod * fac[k + 1] % mod * fac[k] % mod);
}
printf("%d ", ans);
}
printf("\n");
return 0;
}
T3 Number
我好菜……不会生成函数，也不会线性代数……
设 \(f_{i,j}\) 表示在第 \(i\) 次操作后原数为 \(j\) 的概率，存在转移：
\[f_{i,j}=\sum_{w=j}^{n}\tfrac{f_{i-1,w}}{w+1}
\]
转移很有规律但是不好优化，考虑用生成函数刻画关系，设 \(F_i(x)=\sum_{k=0}^{n}f_{i,k}x^k\) ，那么
\[\begin{aligned}
F_i(x)&=\sum_{k=0}^{n}f_{i,k}x^k\\
&=\sum_{k=0}^{n}\sum_{w=k}^{n}\tfrac{f_{i-1,w}}{w+1}x^k\\
&=\sum_{w=0}^{n}\tfrac{f_{i-1,w}}{w+1}\sum_{k=0}^{w}x^k\\
&=\sum_{w=0}^{n}\tfrac{f_{i-1,w}}{w+1}\times\tfrac{x^{w+1}-1}{x-1}\\
&=\tfrac{1}{x-1}\sum_{w=0}^{n}f_{i-1,w}\times\tfrac{x^{w+1}-1}{w+1}\\
&=\tfrac{1}{x-1}\sum_{w=0}^{n}f_{i-1,w}\int_1^x t^wdt\\
&=\tfrac{1}{x-1}\int_1^xF_{i-1}(t)dt
\end{aligned}
\]
这个 \(\int_1^xF_{i-1}(t)dt\) 看起来非常邪恶，考虑换成更常用的 \(\int_0^x\) （我从来没用过就是了），设 \(G_i(x)=F_i(x+1)\) ，同时设 \(G_i(x)=\sum_{k=0}^{n}g_{i,k}x^k\)， 那么：
\[\begin{aligned}
G_i(x)&=F_i(x+1)\\
&=\tfrac{1}{x}\int_1^{x+1}F_{i-1}(t)dt\\
&=\tfrac{1}{x}\int_0^{x}F_{i-1}(t+1)d(t+1)\\
&=\tfrac{1}{x}\int_0^{x}G_{i-1}(t)dt\\
&=\sum_{k=0}^{n}\tfrac{g_{i-1,k}}{k+1}x^k
\end{aligned}
\]
容易发现 \(g_{i,k}=\tfrac{g_{i-1,k}}{k+1}\) ，那么 \(g_{m,k}=\tfrac{g_{0,k}}{(k+1)^m}\) ，这十分友好，因此只需要考虑 \(f,g\) 数组之间的相互转化即可。
根据定义 \(G_i(x)=F_i(x+1)\) ，那么：
\[\begin{aligned}
G_i(x)&=F_i(x+1)\\
&=\sum_{k=0}^{n}f_{i,k}(x+1)^{k}\\
&=\sum_{k=0}^{n}f_{i,k}\sum_{w=0}^{k}\binom{k}{w}x^w\\
&=\sum_{w=0}^{n}\sum_{k=w}^{n}f_{i,k}\binom{k}{w}x^w
\end{aligned}
\]
因此 \(g_{i,w}=\sum_{k=w}^{n}f_{i,k}\binom{k}{w}\) ，那么：
\[\begin{aligned}
g_{i,w}&=\sum_{k=w}^{n}f_{i,k}\binom{k}{w}\\
&=\tfrac{1}{w!}\sum_{k=w}^{n}f_{i,k}k!\tfrac{1}{(k-w)!}\\
&=\tfrac{1}{w!}\sum_{k=0}^{n-w}f_{i,k+w}(k+w)!\tfrac{1}{k!}
\end{aligned}
\]
设 \(h_{i,k}=f_{i,n-k}(n-k)!\) ，那么：
\[g_{i,w}=\tfrac{1}{w!}\sum_{k=0}^{n-w}h_{i,n-k-w}\tfrac{1}{k!}
\]
很容易使用 NTT 优化。
将 \(g\) 转化为 \(f\) 的过程可以使用二项式反演，推导过程和上述过程基本相同，在此不在赘述。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e5;
const int mod = 998244353, gmod = 3;
int n;
long long m;
int bit, total, rev[max1 * 4 + 5];
int f[max1 * 4 + 5], g[max1 * 4 + 5];
int inv[max1 * 4 + 5], fac[max1 * 4 + 5], ifac[max1 * 4 + 5];
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
void Iterative_NTT ( int A[], int type, int len )
{
for ( int i = 0; i < len; i ++ )
if ( i < rev[i] )
swap(A[i], A[rev[i]]);
for ( int mid = 2; mid <= len; mid <<= 1 )
{
int wn = Quick_Power(gmod, ( mod - 1 ) / mid);
if ( type == -1 )
wn = Quick_Power(wn, mod - 2);
for ( int i = 0; i < len; i += mid )
{
int w = 1;
for ( int k = 0; k < mid >> 1; k ++ )
{
int x = A[i + k], y = 1LL * w * A[i + ( mid >> 1 ) + k] % mod;
A[i + k] = ( x + y ) % mod;
A[i + ( mid >> 1 ) + k] = ( x - y + mod ) % mod;
w = 1LL * w * wn % mod;
}
}
}
if ( type == -1 )
{
int T = Quick_Power(len, mod - 2);
for ( int i = 0; i < len; i ++ )
f[i] = 1LL * f[i] * T % mod;
}
return;
}
int main ()
{
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
scanf("%d%lld", &n, &m);
m %= mod - 1;
for ( int i = 0; i <= n; i ++ )
scanf("%d", &f[i]);
bit = 1, total = 2;
while ( total < n + n + 1 )
total <<= 1, ++bit;
rev[0] = 0;
for ( int i = 1; i < total; i ++ )
rev[i] = ( rev[i >> 1] >> 1 ) | ( i & 1 ) << bit - 1;
inv[1] = 1;
for ( int i = 2; i <= n; i ++ )
inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
fac[0] = ifac[0] = 1;
for ( int i = 1; i <= n; i ++ )
{
fac[i] = 1LL * fac[i - 1] * i % mod;
ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
}
for ( int i = 0; i <= n; i ++ )
f[i] = 1LL * f[i] * fac[i] % mod;
reverse(f, f + 1 + n);
for ( int i = 0; i <= n; i ++ )
g[i] = ifac[i];
for ( int i = n + 1; i < total; i ++ )
f[i] = g[i] = 0;
Iterative_NTT(f, 1, total);
Iterative_NTT(g, 1, total);
for ( int i = 0; i < total; i ++ )
f[i] = 1LL * f[i] * g[i] % mod;
Iterative_NTT(f, -1, total);
for ( int i = 0; i <= n; i ++ )
f[i] = 1LL * f[i] * Quick_Power(Quick_Power(n - i + 1, m), mod - 2) % mod;
for ( int i = 0; i <= n; i ++ )
{
if ( i & 1 )
g[i] = mod - ifac[i];
else
g[i] = ifac[i];
}
for ( int i = n + 1; i < total; i ++ )
f[i] = g[i] = 0;
Iterative_NTT(f, 1, total);
Iterative_NTT(g, 1, total);
for ( int i = 0; i < total; i ++ )
f[i] = 1LL * f[i] * g[i] % mod;
Iterative_NTT(f, -1, total);
reverse(f, f + 1 + n);
for ( int i = 0; i <= n; i ++ )
f[i] = 1LL * f[i] * ifac[i] % mod;
for ( int i = 0; i <= n; i ++ )
printf("%d ", f[i]);
printf("\n");
return 0;
}