大学网站模板html,网站开发的排期,游戏app制作,手机开发者模式怎么开P3301 [SDOI2013]方程
题意#xff1a; 题解#xff1a;
插板法介绍
首先要先讲组合数学的一个方法#xff1a;插板法 问题引出#xff1a;把10个球放进三个盒子#xff0c;每个箱子至少一个有多少种分法#xff1f; 10个球就有9个空隙#xff0c;我们可以考虑在这个…P3301 [SDOI2013]方程
题意 题解
插板法介绍
首先要先讲组合数学的一个方法插板法 问题引出把10个球放进三个盒子每个箱子至少一个有多少种分法 10个球就有9个空隙我们可以考虑在这个9个空隙中放入两个隔板这样10个球就被分成了3组就相当于放入了三个箱子。 答案就是C10−13−1C_{10-1}^{3-1}C10−13−1 也就是n个球放入m个盒子每个箱子至少一个有Cn−1m−1C_{n-1}^{m-1}Cn−1m−1种分法 问题2把10个球放进三个盒子有多少种分法 此时箱子内可以没有球我们可以预先在3个盒子里都放一个球则问题转化为将13个球放进3个盒子里每个盒子至少一个有多少中放法。答案为C122C_{12}^2C122 也就是n个球放入m个盒子有Cnm−1m−1C_{nm-1}^{m-1}Cnm−1m−1种分法
本题讲解
如果没有限制就是求x1x2..xnMx_{1}x_{2}..x_{n}Mx1x2..xnM,这不就相当于把M分配到n个箱子里且每个箱子不能为空这样答案就是CM−1n−1C_{M-1}^{n-1}CM−1n−1 但是题目有两类限制
第二类限制为XiAiX_{i}A_{i}XiAi,我们可以巧妙的转化对于第i个箱子要求分配数要大于AiA_{i}Ai那我们可以认为先将Ai−1A_{i}-1Ai−1分配给XiX_{i}Xi然后剩下还是老分法(分配给n个箱子,每个箱子至少一个)。这种方法M要减去Ai−1A_{i}-1Ai−1(相当于提前分配了)
对于第一类限制XiAiX_{i}A_{i}XiAi就比较麻烦了,不过题目中限制数最大为8我们可以用容斥解决 先计算不考虑前n1个数的限制方案数-前n1个数至少有一个不满足条件的方案数前n1个数至少有2个不满足条件的方案数-… 代码具体就是枚举状态S,其二进制状态下第i位为1表示计算了第i个数如果有奇数个1就是减偶数个1就是加 因为nm很大且p不一定为质数所以用扩展卢卡斯 容斥代码
for (int s 0; s (1 n1) - 1; s) {int num 0;ll now m;for (int i 1; i n1; i) {if ((1 (i - 1)) s) {now- a[i];num;}}ll tmp exLucas(now - 1, n - 1, mod);// printf(tmp%lld\n,tmp);ans (ans ((num 1) ? (mod - tmp) % mod : tmp)) % mod;}这样做70分会被卡常 题目所给的模数只有三种 2622034142∗3∗11∗397∗10072622034142*3*11*397*10072622034142∗3∗11∗397∗1007 43736787553∗73∗10124373678755^3*7^3*101^243736787553∗73∗1012 10007是质数10007是质数10007是质数 这样可以省去扩展卢卡斯分析qk的过程大大减少常数 同时优化一下扩展卢卡斯处理阶乘的过程提前计算好这样也可以大力卡常。不然根本卡不过去。
代码
// Problem: P3301 [SDOI2013]方程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3301
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Data:2021-08-27 16:25:48
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
ll mod;void exgcd(ll a, ll b, ll x, ll y)
{if (!b) {x 1, y 0;return;}exgcd(b, a % b, y, x);y- a / b * x;return;
}inline ll inv(ll n, ll p)
{ll x, y;exgcd(n, p, x, y);return (x p) % p;
}ll qpow(ll base, ll p, ll mod)
{ll ret 1;for (; p; p 1, base base * base % mod)if (p 1)ret ret * base % mod;return ret;
}ll CRT(int n, ll* a, ll* m)
{ll M 1, ret 0;for (ll i 1; i n; i)M* m[i];for (ll i 1; i n; i) {ll w M / m[i];ret (ret a[i] * w % mod * inv(w, m[i]) % mod) % mod;}return (ret mod) % mod;
}
int retfac[10];
ll calc(ll n, ll q, ll qk,ll retfac)
{if (!n)return 1;ll ret retfac;ret qpow(ret, n / qk, qk);for (ll i n / qk * qk 1; i n; i)if (i % q)ret ret * (i % qk) % qk;return ret * calc(n / q, q, qk,retfac) % qk;
}ll multiLucas(ll n, ll m, ll q, ll qk,ll retfac)
{int cnt 0;for (ll i n; i; i/ q)cnt i / q;for (ll i m; i; i/ q)cnt- i / q;for (ll i n - m; i; i/ q)cnt- i / q;return qpow(q, cnt, qk) * calc(n, q, qk,retfac) % qk * inv(calc(m, q, qk,retfac), qk) % qk * inv(calc(n - m, q, qk,retfac), qk) % qk;
}int cnt;
ll qk[20];
ll qw[20];
ll exLucas(ll n, ll m, ll p)
{if(mn)return 0;ll a[20];
// int cnt 0;
// ll qk[20], a[20]; //存放所有的 q^k 和待合并答案的结果
//
// for (ll i 2; i * i p; i) //质因数分解
// {
// if (p % i 0) {
// qk[cnt] 1;
// while (p % i 0)
// qk[cnt]* i, p/ i;
// a[cnt] multiLucas(n, m, i, qk[cnt]);
// }
// }
// if (p 1)
// qk[cnt] p, a[cnt] multiLucas(n, m, p, p);for(int i1;icnt;i){a[i]multiLucas(n, m,qw[i] , qk[i],retfac[i]);}return CRT(cnt, a, qk); //CRT 合并答案
}
void init(ll p) {for (ll i 2; i * i p; i) //质因数分解{if (p % i 0) {qk[cnt] 1;qw[cnt]i;while (p % i 0)qk[cnt]* i, p/ i;}}if (p 1)qk[cnt] p,qw[cnt]p;for(int i1;icnt;i){retfac[i]1;for(int j1;jqk[i];j){if(j%qw[i]){retfac[i] 1ll * retfac[i] * j % qk[i];}}}
}ll t;
const int maxn 10;
int a[maxn], b[maxn];
ll n, n1, n2, m;
void init(){}
int main()
{//rd_test();read(t, mod);init(mod);//预处理不然会t三个点 while (t--) {read(n, n1, n2, m);for (int i 1; i n1; i)read(a[i]);for (int i 1; i n2; i) {read(b[i]);m- (b[i] - 1);}//ll sumexLucas(m-1,n-1,mod);ll ans 0;for (int s 0; s (1 n1) - 1; s) {int num 0;ll now m;for (int i 1; i n1; i) {if ((1 (i - 1)) s) {now- a[i];num;}}ll tmp exLucas(now - 1, n - 1, mod);// printf(tmp%lld\n,tmp);ans (ans ((num 1) ? (mod - tmp) % mod : tmp)) % mod;}printf(%lld\n, ans);}return 0;//Time_test();
}
