題目鏈接

BZOJ：https://www.lydsy.com/JudgeOnline/problem.php?id=2655

Solution

設\(f_i\)表示長度為\(i\)的序列個數，\(g_{i,x}\)表示含有\(x\)的序列個數，注意這里不考慮順序，順序答案直接乘\(n!\)就好了。

首先很顯然可以得到：
\[ f_i=\frac{1}{n}\sum_{x=1}^{A}g_{i,x} \]
我們嘗試向\(f_i\)中添加一個\(x\)，可以得到：
\[ xf_i=xg_{i,x}+g_{i+1,x} \]
把這個式子變一下：
\[ g_{i,x}=xf_{i-1}-xg_{i-1,x} \]
注意到這是個遞歸的形式，可以得到：
\[ g_{n,x}=\sum_{i=1}^{n}(-1)^{i-1}x^if_{n-i} \]
根據第一個式子累和：
\[ f_n=\frac{1}{n}\sum_{i=1}^Ag_{n,x}=\frac{1}{n}\sum_{i=1}^{A}\sum_{j=1}^{n}(-1)^{j-1}i^{j}f_{n-j}=\frac{1}{n}\sum_{j=1}^{n}\left((-1)^{j-1}\sum_{i=1}^{A}i^j\right)f_{n-j} \]
注意中間是一個只和\(j\)有關的式子，我們可以插值做到\(O(n)\)算一次。

那么我們預處理中間，其他的爆算就好了，復雜度\(O(n^2)\)。

注意我代碼偷懶多了個\(\log\)，但是不影響。

#include<bits/stdc++.h> using namespace std;void read(int &x) {x=0;int f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; }void print(int x) {if(x<0) putchar('-'),x=-x;if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}#define lf double #define ll long long #define pii pair<int,int > #define vec vector<int >#define pb push_back #define mp make_pair #define fr first #define sc second#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 600+10; const int inf = 1e9; const lf eps = 1e-8;int g[maxn],f[maxn],y[maxn],mod,fac[maxn],ifac[maxn],inv[maxn],suf[maxn],pre[maxn];int qpow(int a,int x) {int res=1;for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;return res; }int power_sum(int n,int k) {fac[0]=ifac[0]=1;k+=2;for(int i=1;i<=k;i++) y[i]=(y[i-1]+qpow(i,k-2))%mod;for(int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod,ifac[i]=qpow(fac[i],mod-2);pre[0]=1;for(int i=1;i<=k;i++) pre[i]=1ll*pre[i-1]*(n-i)%mod;suf[k+1]=1;for(int i=k;i;i--) suf[i]=1ll*suf[i+1]*(n-i)%mod;int res=0;for(int i=1;i<=k;i++) res=(res+1ll*(((k-i)&1)?-1:1)*y[i]*pre[i-1]%mod*suf[i+1]%mod*ifac[i-1]%mod*ifac[k-i]%mod)%mod; return (res+mod)%mod; }int A,n;int main() {read(A),read(n),read(mod);for(int i=0;i<=n;i++) g[i]=((i&1)?1:-1)*power_sum(A,i);f[0]=1;int t=1;for(int i=1;i<=n;i++) {for(int j=1;j<=i;j++)f[i]=(f[i]+1ll*g[j]*f[i-j])%mod;f[i]=1ll*f[i]*qpow(i,mod-2)%mod;t=1ll*t*i%mod;}write((1ll*f[n]*t%mod+mod)%mod);return 0; }

轉載于:https://www.cnblogs.com/hbyer/p/10890702.html

總結

以上是生活随笔為你收集整理的[BZOJ2655] calc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。