我的Lucas竟然这么糟糕

题目

3129: [Sdoi2013]方程

Time Limit: 30 Sec Memory Limit: 256 MB

Description

给定方程\(X_1+X_2+...+X_n=M\),我们对第\(l..n_1\)个变量进行一些限制: \(X_l <= A_1\),\(X_2 <= A_2\),\(X_{n_1} <= A_{n_1}\) 我们对第\(n_1+1..n_1+n_2\)个变量进行一些限制: \(X_{n_1+1} >= A_{n_1+1}\)…以此类推 求:在满足这些限制的前提下,该方程正整数解的个数。 答案可能很大,请输出对\(p\)取模后的答案,也即答案除以\(p\)的余数。

Input

输入含有多组数据,第一行两个正整数\(T\)\(p\)\(T\)表示这个测试点内的数据组数,\(p\)的含义见题目描述。 对于每组数据,第一行四个非负整数\(n\),\(n_1\)\(n_2\)\(m\)。 第二行\(n_l+n_2\)个正整数,表示\(A_{1 \to n_1+n_2}\)注意.

Output

\(T\)行,每行一个正整数表示取模后的答案。

HINT

\(n <= 10^9\), \(n_1 <= 8\), \(n_2 <= 8\),\(m <= 10^9\),\(p <=437367875\) 对于\(l00\%\)的测试数据\(T <= 5\)\(1 <= A_{1 \to n_1+n_2} <= m\)\(n_1+n_2 <= n\) #解题报告 考场上被卡常了只有80分,幸好bzoj上给了整整30s,就A掉了. 首先想的是:\(X_{i=n_1+1 \to n_2+n_1} >= A_i\) 是很容易处理的,只需要令\(X_i=A_{i-1}+d_i\)带入原式化简就可以得到,这样\(d_i\)的限制就只是正整数了. 既然我们会处理\(>=\)的情况,对于\(<=\)的情况就可以容斥,怎么容斥?每次枚举哪些条件一定不符合,这样就可以按照\(>\)的情况转化,然后用总方案\(-\)奇数不符合\(+\)偶数不符合,\(-+-+...\)就可以得到最终的答案! 最难的地方出现了:如何计算方案数?容易得到是插板法裸题,但是模合数意义下的组合数?只能用拓展lucas定理! 将狼踩尽前辈介绍的很详细 # 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
typedef long long LL;
int T,mod;
int n,n1,n2,m,ans;
int a[20];
LL Pow(LL n,LL m,LL mod) {
LL ans=1;
while(m>0) {
if(m & 1) ans=(LL)ans*n%mod;
n=(LL)n*n%mod; m >>= 1;
}
return ans;
}
LL Pow(LL n,LL m) {
LL ans=1;
while(m>0) {
if(m & 1) ans=ans*n;
n=n*n; m >>= 1;
}
return ans;
}
LL x,y;
LL exgcd(LL a,LL b) {
if(a==0) {
x=0,y=1;
return b;
}LL r=exgcd(b%a,a);
LL t=x; x=y - (b/a)*x; y=t;
return r;
}
LL rev(LL a,LL b) { exgcd(a,b); return ((x%b)+b)%b; }
LL Calc(LL n,LL p,LL t) {
if(n==0) return 1;
LL s=Pow(p,t),k=n/s,tmp=1;
for(LL i=1;i<=s;i++) if(i%p)tmp=(LL)tmp*i%s;
LL ans=Pow(tmp,k,s);
for(LL i=s*k+1;i<=n;i++)
if(i%p) ans=(LL)ans*i%s;
return (LL)ans*Calc(n/p,p,t)%s;
}
LL C(LL n,LL m,LL p,LL t) {
LL s=Pow(p,t),q=0;
for(LL i=n;i;i/=p) q += i / p;
for(LL i=m;i;i/=p) q -= i / p;
for(LL i=n-m;i;i/=p) q -= i / p;
LL ans=Pow(p,q);
LL a=Calc(n,p,t),b=Calc(m,p,t),c=Calc(n-m,p,t);
return (LL)(ans*a%s*rev(b,s)%s*rev(c,s))%s;
}
LL China(LL A[],LL M[],LL cnt) {
LL ans=0,m,n=1;
for(LL i=1;i<=cnt;i++) n *= M[i];
for(LL i=1;i<=cnt;i++) {
m=n / M[i];
exgcd(M[i],m);
ans=(ans+(LL)y*m*A[i])%n;
}
return (ans+n)%n;
}
LL A[maxn],M[maxn],q[maxn],tt[maxn],cnt;
LL Lucas(LL n,LL m,LL mod) {
if (n<m) return 0;
for (int i=1;i<=cnt;i++)
A[i]=C(n,m,q[i],tt[i]);
return China(A,M,cnt);
}
bool cho[10];
inline void cal(int have) {
int mm=m;
for (int i=1;i<=n1;i++)
if (cho[i])
mm-=a[i];
memset(A,0,sizeof(A));
if (have&1)
ans=((ans-Lucas(mm-1,n-1,mod))%mod+mod)%mod;
else
ans=(ans+Lucas(mm-1,n-1,mod))%mod;
}
void dfs(int x,int have) {
if (x==n1+1)
cal(have);
else{
cho[x]=0;
dfs(x+1,have);
cho[x]=1;
dfs(x+1,have+1);
cho[x]=0;
}
}
int main() {
scanf("%d%d",&T,&mod);
LL mmod=mod;
for(LL i=2;i*i<=mmod;i++) if(mmod%i==0) {
LL t=0;
while(mmod%i==0) t++,mmod /= i;
q[++cnt]=i;
tt[cnt]=t;
M[cnt]=Pow(i,t);
}if(mmod>1) {
q[++cnt]=mmod;
tt[cnt]=1;
M[cnt]=Pow(mmod,1);
}
while (T--) {
ans=0;
scanf("%d%d%d%d",&n,&n1,&n2,&m);
for (int i=1;i<=n1;i++)
scanf("%d",&a[i]);
for (int i=n1+1;i<=n1+n2;i++)
scanf("%d",&a[i]);
for (int i=n1+1;i<=n1+n2;i++)
m-=(a[i]-1);
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}

留言