Description
定义长度为 \(n\) 的“交错序列”为：长度为 \(n\) 序列中仅含 \(0,1\) 且没有相邻的 \(1\) 。给出 \(a,b\) ，假设序列中有 \(x\) 个 \(0\) ， \(y\) 个 \(1\) 。定义该“交错序列”的价值为 \(x^a\times y^b\) ，特别地 \(0^0=1\) 。求所有长度为 \(n\) 的交错序列的价值的和。对质数 \(m\) 取模。
\(1\leq n\leq 10000000,1\leq m\leq 100000000,1\leq a,b\leq 45\)
Solution
傻逼题啊，组合数+ \(lucas\) 乱搞一下就好了。
式子就是： \(\sum\limits_{i=0}^{\left\lfloor\frac{n+1}{2}\right\rfloor}(n-i)^a\times i^b\times{n-i+1\choose i}\)
正好 \(O(n)\) ，乱搞交了
あら？ \(lucas\) 也有个 \(\log\) 啊！！！ f**k ， 45pts 。
观察式子 \(x^a\times y^b\) ，等价于 \((n-y)^a\times y^b\) 。
即
\[\sum_{i=0}^a{a\choose i}(-1)^{a-i}n^iy^{a+b-i}\]
那么我们只要算出 \(y^i\) ，最后乘上 \({a\choose i}(-1)^{a-i}n^i\) 即可。
记 \(f_{i,j,0/1}\) 表示长度为 \(i\) 的序列结尾为 \(0/1\) 且所有 \(1\) 的个数（即式子中的 \(y\) ）的 \(j\) 次方和。
考虑转移，注意到如果这一位填 \(0\) ，那么是与式子中的 \(y\) 无关的，显然
\[f_{i-1,j,0}+f_{i-1,j,1}\rightarrow f_{i,j,0}\]
如果这一位填 \(1\) ，假设 \(y'=y+1\) ，那么 \(y'^i=(y+1)^i=\sum\limits_{j=0}^i {i\choose j}y^j\)
那么，
\[\sum_{k=0}^j{j\choose k}f_{i-1,k,0}\rightarrow f_{i,j,1}\]
初值 \(f_{0,0,0}=1\) ，长度为 \(0\) 含有 \(0\) 个 \(1\) 。可以用矩阵乘法加速。
复杂度 \(O((2(a+b))^3\log_2 n)\) 。有点卡常...
Code
45pts
#include <bits/stdc++.h>
using namespace std;
const int N = 10000000+5;
int n, m, a, b, ifac[N], fac[N];
int quick_pow(int a, int b) {
int ans = 1;
while (b) {
if (b&1) ans = 1ll*ans*a%m;
b >>= 1, a = 1ll*a*a%m;
}
return ans;
}
int C(int n, int m, int p) {
if (n < m) return 0;
return 1ll*fac[n]*ifac[m]%p*ifac[n-m]%p;
}
int lucas(int n, int m, int p) {
if (!m || n == m) return 1; if (n < m) return 0;
return 1ll*lucas(n/p, n/p, p)*C(n%p, m%p, p)%p;
}
void work() {
scanf("%d%d%d%d", &n, &a, &b, &m);
int l = min(n+1, m);
ifac[0] = ifac[1] = fac[0] = fac[1] = 1;
for (int i = 2; i < l; i++) ifac[i] = -1ll*(m/i)*ifac[m%i]%m;
for (int i = 2; i <= l; i++)
ifac[i] = 1ll*ifac[i]*ifac[i-1]%m,
fac[i] = 1ll*i*fac[i-1]%m;
int ans = 0;
for (int i = 0; i*2-1 <= n; i++) {
(ans += 1ll*quick_pow(n-i, a)*quick_pow(i, b)%m*lucas(n-i+1, i, m)%m) %= m;
}
printf("%d\n", (ans+m)%m);
}
int main() {work(); return 0; }100pts
#include <bits/stdc++.h>
using namespace std;
const int N = 200+5;
int n, a, b, m, C[N][N], sz1, sz2;
struct mat {
int a[N][N];
mat() {}
mat operator * (const mat &b) const {
mat ans;
for (int i = 0; i < sz2; i++)
for (int j = 0; j < sz2; j++) {
ans.a[i][j] = 0;
for (int k = 0; k < sz2; k++)
if (a[i][k] && b.a[k][j])
(ans.a[i][j] += 1ll*a[i][k]*b.a[k][j]%m) %= m;
}
return ans;
}
}S, T;
void work() {
scanf("%d%d%d%d", &n, &a, &b, &m);
sz1 = a+b+1, sz2 = sz1<<1;
for (int i = 0; i <= sz1; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1]+C[i-1][j])%m;
}
for (int i = 0; i < sz1; i++) {
T.a[i][i] = 1, T.a[i+sz1][i] = 1;
for (int j = i; j < sz1; j++) T.a[i][j+sz1] = C[j][i];
}
S.a[0][0] = 1; int t = n;
while (t) {
if (t&1) S = S*T;
T = T*T, t >>= 1;
}
int ans = 0;
for (int i = 0, pw = 1; i <= a; i++, pw = 1ll*pw*n%m) {
ans += 1ll*((a-i)&1 ? -1 : 1)*C[a][i]*pw%m*(S.a[0][a+b-i]+S.a[0][a+b+sz1-i])%m;
ans %= m;
}
printf("%d\n", (ans+m)%m);
}
int main() {work(); return 0; }