任意模数多项式乘法逆
多项式F与其乘法逆G相乘后，除常数项为1外，其他项系数都为0
由此列出式子，移项后就很明显能O（n^2）求出G1～Gn了
后面其实就是个矩阵加速数列递推了，特判完前n项后，直接矩阵快速幂就完了
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int maxk = 15;
int n, K, mod, f[maxk], g[maxk];
struct Mat {
int a[maxk][maxk];
Mat() { memset(a, 0, sizeof a); }
void Init() {
for(int i = 1;i <= K; ++i) a[i][i] = 1;
}
Mat operator * (const Mat &B) const {
Mat ans;
for(int i = 1;i <= K; ++i) {
for(int j = 1;j <= K; ++j) {
for(int k = 1;k <= K; ++k) {
(ans.a[i][j] += (ll)a[i][k]*B.a[k][j]%mod)%=mod;
}
}
}
return ans;
}
};
Mat fp(Mat a, int x) {
Mat ans; ans.Init();
for(;x > 0;x >>= 1, a = a*a)
if(x&1) ans = ans*a;
return ans;
}
int main() {
freopen("poly.in","r",stdin);
freopen("poly.out","w",stdout);
scanf("%d%d%d", &n, &K, &mod);
for(int i = 1;i <= K; ++i) scanf("%d", &f[i]);
g[0] = 1;
for(int i = 1;i <= K; ++i) {
int now = 0;
for(int j = 1;j <= i; ++j) (now -= (ll)f[j]*g[i-j]%mod)%=mod;
g[i] = (now%mod+mod)%mod;
}
if(n <= K) return printf("%d
", g[n]), 0;
Mat F, G;
for(int i = 1;i <= K; ++i) G.a[i][1] = g[K-i+1];
for(int i = 1;i <= K; ++i) F.a[1][i] = mod-f[i];
for(int i = 2;i <= K; ++i) F.a[i][i-1] = 1;
G = fp(F, n-K)*G;
printf("%d
", G.a[1][1]);
return 0;
}
明明的随机数
-
先求出k1行k2列各行各列都不相同的情况，要用到n^2递推第一类斯特林数，斯特林反演
-
然后乘以第二类斯特林数S2(n,k1)*S2(m,k2)就行了，这两个数可以O(klogn)求
对于第一步直接搬题解了
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int mod = 998244353;
int n, m, c, k1, k2;
int s1[3005][3005], fac[3005], fy[3005], f[3005], g[3005];
int fp(int a, int x, int ans = 1) {
for(;x > 0;x >>= 1, a = (ll)a*a%mod) if(x&1) ans = (ll)ans*a%mod;
return ans;
}
int C(int x, int y) {
return (x<y||y<0) ? 0 : (ll)fac[x]*fy[y]%mod*fy[x-y]%mod;
}
void Init() {
s1[0][0] = fac[0] = fy[0] = 1;
for(int i = 1;i <= 3000; ++i) for(int j = 1;j <= i; ++j) s1[i][j] = (s1[i-1][j-1]+(ll)s1[i-1][j]*(i-1)%mod)%mod;
for(int i = 1;i <= 3000; ++i) fac[i] = (ll)fac[i-1]*i%mod;
fy[3000] = fp(fac[3000], mod-2);
for(int i = 3000;i > 1; --i) fy[i-1] = (ll)fy[i]*i%mod;
}
int S2(int n, int m) {
int S = 0;
for(int i = 0;i <= m; ++i) {
if(i&1) (S += mod-(ll)C(m, i)*fp(m-i, n)%mod)%=mod;
else (S += (ll)C(m, i)*fp(m-i, n)%mod)%=mod;
}
return (ll)S*fy[m]%mod;
}
int main() {
freopen("random.in","r",stdin);
freopen("random.out","w",stdout);
Init();
int cs; scanf("%d", &cs);
while(cs --> 0){
scanf("%d%d%d%d%d", &n, &m, &k1, &k2, &c);
if(c == 1) { printf("%d
", k1==1&&k2==1);continue; }
if(k1 == k2 && k1 == 1) { printf("%d
", c%mod);continue; }
for(int i = 1;i <= k1; ++i) {
int now = 1, lst = fp(c, i);
for(int j = 1;j <= k2; ++j) now = (ll)now*(lst-j+1)%mod;
f[i] = (now%mod+mod)%mod;
g[i] = 0;
for(int j = 1;j <= i; ++j) {
if((i-j)&1) (g[i] += mod-(ll)s1[i][j]*f[j]%mod)%=mod;
else (g[i] += (ll)s1[i][j]*f[j]%mod)%=mod;
}
}
printf("%lld
", (ll)g[k1]*S2(n, k1)%mod*S2(m, k2)%mod);
}
return 0;
}
凯爹博弈
又现学了点博弈论，SG函数，不过这道题先咕了
Code