例题
1，P3301 方程
题意:
给定方程
\[X_1+X_2+\dots+X_n=M
\]
有限制如下：
\[\begin{align*}
&X_1\leq A_1\\&X_2\leq A_2\\&\dots\\&X_{n_1}\leq A_{n_1},\\\\&X_{n_1+1}\geq A_{n_1+1}\\&X_{n_1+2}\geq A_{n_1+2}\\&\dots\\&X_{n_1+n_2}\geq A_{n_1+n_2}
\end{align*}
\]
其中 \(n_1+n_2\leq n,\;n\leq 1e^9,n_1\leq8,n_2\leq8,m\leq1e^9\)。
求：满足这些限制的前提下，该方程正整数解的个数。答案对 \(p\) 取模。 \(p\in\{10007,262203414,437367875\}\) 。
解：
对于所有含限制 \(X_i\geq A_i\) 的 \(X_i\) 做变换：
\[X_i=X_i-A_i\\M-=A_i
\]
则 \(X_i\) 的限制变为 \(X_i\geq0\) 。
则，给定方程的解的个数 \(a_M\) 为
\[\begin{align*}
f(x)&=\frac{1}{(1-x)^{n-n_1}}\times \frac{\prod_{i=1}^{n_1}(1-x^{A_i})}{(1-x)^{n_1}}\\&=\frac{\prod_{i=1}^{n_1}(1-x^{A_i})}{(1-x)^n}
\end{align*}
\]
的展开式中 \(x^{M}\) 的系数。
剩下做法同例2。
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;y=0;
return a;
}
ll g=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return g;
}
ll inv(ll a,ll b)
{
ll x=0,y=0;
exgcd(a,b,x,y);
x=(x%b+b)%b;
if(!x)x+=b;
return x;
}
ll kpow(ll a,ll b,ll p)
{
ll ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
ll Y[maxn];
ll calc(ll n,ll p,ll pk,ll yy)
{
if(!n)return 1;
ll x=calc(n/p,p,pk,yy),y=1;
ll z=1;
// for(ll i=1;i<=pk;i++)
// if(i%p)y=y*i%pk;
y=kpow(yy,n/pk,pk);
for(ll i=n/pk*pk;i<=n;i++)
if(i%p)z=z*i%pk;
return x*y%pk*z%pk;
}
ll G(ll n,ll p){
if(n return n/p+G(n/p,p); } ll fac[maxn],w[maxn],b[maxn],k,tw[maxn]; ll exLucas(ll n,ll m,ll p) { for(int i=1;i<=k;i++) { tw[i]=w[i]; b[i]=kpow(fac[i],G(n,fac[i])-G(m,fac[i])-G(n-m,fac[i]),w[i]); b[i]=b[i]*calc(n,fac[i],w[i],Y[i])%w[i]*inv(calc(m,fac[i],w[i],Y[i]),w[i])%w[i]*inv(calc(n-m,fac[i],w[i],Y[i]),w[i])%w[i]; } ll d; for(int i=2;i<=k;i++) { d=__gcd(tw[i-1],tw[i]); b[i]=inv(tw[i-1]/d,tw[i]/d)*((b[i]-b[i-1])/d)%(tw[i]/d)*tw[i-1]+b[i-1]; tw[i]=tw[i-1]*tw[i]/d; b[i]=(b[i]%tw[i]+tw[i])%tw[i]; } return b[k]; } ll A[maxn]; map int main() { int T,p,pp; scanf("%d%d",&T,&p); pp=p;k=0; for(int i=2,t;i*i<=pp;i++) if(pp%i==0){ t=1; while(pp%i==0)pp/=i,t*=i; w[++k]=t;fac[k]=i; } if(pp!=1){ w[++k]=pp;fac[k]=pp; } for(int i=1;i<=k;i++) { Y[i]=1; for(ll j=1;j<=w[i];j++) if(j%fac[i])Y[i]=Y[i]*j%w[i]; } while(T--) { mp.clear(); ll n,n1,n2,m,x,r; scanf("%lld%lld%lld%lld",&n,&n1,&n2,&m); for(int i=1;i<=n1;i++)scanf("%lld",&A[i]); for(int i=1;i<=n2;i++){ scanf("%lld",&x); m-=x; } m-=(n-n2); if(m<0){ puts("0");continue; } mp[0]=1; ll c,d; for(int i=1;i<=n1;i++) { tmp.clear(); for(auto x:mp){ c=x.first;d=x.second;// dx^c - dx^(c+a[i]) tmp[c]+=d; tmp[c+A[i]]-=d; } mp=tmp; } ll res=0; for(auto x:mp){ c=x.first;d=x.second; if(c>m)continue; r=m-c; res=(res+d*exLucas(n+r-1,n-1,p)%p+p)%p; } printf("%lld\n",res); } } 2，背包 题意： 给定方程： \[x_1+x_2+x_3+2x_4+2x_5+1+4x_6+x_7+3x_8=n \] 亦即： \[x_1+x_2+x_3+2x_4+2x_5+4x_6+x_7+3x_8=n-1 \] 其中，限制： \[x_1\leq 1\\x_2\leq2\\x_3\leq 3\\x_7\leq1 \] 求解方程非负整数解个数。 解： 对于 \(x_1+x_2+x_3+x_7\) 有母函数： \[(1+x)(1+x+x^2)(1+x+x^2+x^3)(1+x) \] 即： \[\frac{(1-x^2)(1-x^3)(1-x^4)(1-x^2)}{(1-x)^4} \] 对于 \(2x_4+2x_5+4x_6+3x_8\) 有母函数（定理2）： \[\frac{1}{(1-x^2)(1-x^2)(1-x^4)(1-x^3)} \] 则，对于原方程有母函数： \[\begin{align*} f(x)&=\frac{(1-x^2)(1-x^3)(1-x^4)(1-x^2)}{(1-x)^4}\times\frac{1}{(1-x^2)(1-x^2)(1-x^4)(1-x^3)}\\ &=\frac{1}{(1-x)^4} \end{align*} \] 则，原方程的解的个数为 \(f(x)\) 中 \(x^{n-1}\) 的系数，即 \(C_{4+(n-1)-1}^{3}=C_{n+2}^3\) 。 #include #define mem(a,b) memset(a,b,sizeof(a)) #define mkp(a,b) make_pair(a,b) using namespace std; typedef long long ll; const int maxn=1e6+5; const int inf=0x3f3f3f3f; const int mod=1e9+7; int c[4]={1,1,500000004,333333336}; int main() { ll n; scanf("%lld",&n); ll res=1; for(ll i=n+2,j=1;j<=3;i--,j++)res=res*(i%mod)%mod*c[j]%mod; printf("%lld\n",res); }