CSP-S模拟27
今天早上还在被窝里愉悦地睡懒觉，下午就在学校里打上模拟赛了。。。
一上午都处在又困又饿的状态，到了下午稍微好了一点。
T1：喜剧的迷人之处在于
一个挺显然的题，很容易去想到将 \(a\) 去质因数分解，然后直接枚举未配对的因数的倍数即可。
要预处理一个平方数数组，直接二分，时间复杂度是 \(T \sqrt a \log1000000\) 。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 1e6 + 7;
constexpr int INF = 1e18;int T;
int a;
int l;
int r;
int tot;
int ans;
int op[N];
int pri[N];bool st[N];inline int read()
{int x = 0;char c = getchar_unlocked();for(;!isdigit(c);c = getchar_unlocked());for(;isdigit(c);x = x * 10 + c - 48,c = getchar_unlocked());return x;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void init()
{for(int i = 2;i <= 1000000;i ++){if(!st[i]) pri[++ tot] = i;for(int j = 1;j <= tot && pri[j] * i <= 1000000;j ++){st[i * pri[j]] = 1;if(i % pri[j] == 0) break;}}for(int i = 1;i <= 1000000;i ++) op[i] = i * i;
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);init();T = read();while(T --){ans = 1;a = read();l = read();r = read();for(int i = 1,cnt;i <= tot && a > 1;i ++) // sqrt(a) ? {if(a % pri[i] == 0){cnt = 0;while(a % pri[i] == 0) a /= pri[i],cnt ++; cnt %= 2;if(cnt) ans = ans * pri[i];}}int pos = lower_bound(op + 1,op + 1000000 + 1,l / ans) - op; // 大于等于它的if(op[pos] * ans >= l && op[pos] * ans <= r) write(op[pos] * ans),ent;else if(op[pos + 1] * ans >= l && op[pos + 1] * ans <= r) write(op[pos + 1] * ans),ent;else write(-1),ent;}Blue_Archive;
}T2:镜中的野兽
写了一辈子的T2，花半小时写T1，花半小时写T3、T4的暴力，花三小时写T2。。。
是一个比较困难的题（至少对我来说）
首先非常显然的是：一个序列的 \(gcd\) 肯定是 \(lcm\) 的因子。
于是我们就可以枚举倍数（因为题面中给的是 \(gcd\) 和 \(lcm\) 的和）\(k\)。
显然可得 \(gcd\) = \(k\)、\(lcm\) = \(m - k\)。
我们发现这与 \(gcd\) == \(1\) 且 \(lcm\) = \((m - k) / k\) 是等价的，并且下者更好维护（因为有互质）
然后我就不会做了。。。
这就是赛时思路。之后一直尝试找规律，找到了 \(n == 2\) 和 \(n == 3\) 的规律，然后只拿了 25 pts。
考虑如何去计数。
我们发现只有两个限制条件：一个是存在互质，一个是要满足我们找到的 \((m - k) / k\) 是这个序列的 \(lcm\)。
而且发现如果没有这两个条件的话，答案非常好求：直接上组合数就好。
考虑将 \((m - k) / k\) 唯一分解，各个质因子的系数的和中选 \(n\) 个数即为没有限制条件的答案。
然后考虑分别满足这两个条件。
只需要枚举 \(lcm\) 每个质因子，然后直接上容斥即可（啊啊啊，为什么赛时没想出来容斥啊）。
tips：本题也可以直接上莫反去做，因为反演式子还挺板的。（前提是你得会莫比乌斯反演）
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;constexpr int N = 1e5 + 10;int n;
int m;
int mod;
int ans;
int cnt;
int top;
int stk[N];
int tim[N];
int pri[N];
int fac[N];
int inv[N];bool st[N];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{int res = 1;while(b){if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}inline void init(int n)
{fac[0] = inv[0] = 1;for(int i = 1;i <= n;i ++){fac[i] = fac[i - 1] * i % mod;inv[i] = qpow(fac[i],mod - 2);} for(int i = 2;i <= n;i ++){if(!st[i]) pri[++ cnt] = i;for(int j = 1;pri[j] * i <= n && j <= cnt;j ++){st[i * pri[j]] = 1;if(i % pri[j] == 0) break;}}
}inline int C(int n,int m)
{if(n < m) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod;
}inline int F(int x)
{if(x == m) return 0;int op = (m - x) / x;top = 0;for(int i = 1;i <= cnt && pri[i] * pri[i] <= op;i ++){if(op % pri[i]) continue;stk[++ top] = pri[i];tim[top] = 0;while(op % pri[i] == 0) tim[top] ++,op /= pri[i];}if(op > 1){stk[++ top] = op;tim[top] = 1;}int U = (1 << (top * 2)) - 1;int res = 0;for(int S = 0,x;S <= U;S ++) // 枚举每个集合{x = 1;for(int i = 1,u,v;i <= top;i ++) // 看看是不是能达到上界{u = (S >> (i - 1)) & 1;v = (S >> (i + top - 1)) & 1;if(u + v > tim[i] + 1){x = 0;break;}else x *= tim[i] + 1 - u - v;}if(__builtin_popcount(S) & 1) res = (res - C(x,n) + mod) % mod;else res = (res + C(x,n)) % mod;if(!S && x < n) return 0;}return res;
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();mod = read();init(N - 10);for(int i = 1;i * i <= m;i ++){if(m % i != 0) continue;ans = (ans + F(i)) % mod;if(i * i != m) ans = (ans + F(m / i)) % mod;}write(ans);ent;Blue_Archive;
}
T3：我愿相信由你所描述的童话
严格简单于 T2。
考虑两个 \(dp\)。分别是从左往右的贡献和从右往左的贡献。
然后枚举汇合点即可。
直接做的话，时间复杂度是 \(O(n2^m)\)。
不可过（其实可过）。
考虑优化，like 折半搜索，每次查询时枚举前 \(m / 2\) 位的子集查询，修改时枚举后 \(m / 2\) 位的超集修改。
这样可以做到 \(O(n2^{m / 2})\)。
但是我直接找了一篇能过的 \(O(n2^m)\)。
所以代码是 \(O(n2^m)\) 的。
嘻嘻
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 3e5 + 7;
constexpr int M = (1 << 20) + 7;
constexpr int mod = 1e9 + 7;
constexpr int INF = 1e18;int n;
int m;
int ans;
int a[N];
int f[M];
int as[N];
int dp[M];inline int read()
{int x = 0;char c = getchar_unlocked();for(;!isdigit(c);c = getchar_unlocked());for(;isdigit(c);x = x * 10 + c - 48,c = getchar_unlocked());return x;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();for(int i = 1;i <= n;i ++) a[i] = read();for(int i = 1,j,now,op;i <= n;i ++){j = 0,now = a[i];op = max(now & (-now),1ll);as[i] = 1;while(j < now){if((now | j) == now) (as[i] += f[j]) %= mod,j += op;else j += j & (-j);}f[now] = ((f[now] << 1) + as[i]) % mod;}for(int i = n,j,now,op,sum;i >= 1;i --){j = 0;sum = 1;now = a[i];op = max(now & (-now),1ll);while(j <= now){if((now | j) == now) (sum += dp[j]) %= mod,j += op;else j += j & (-j);}(dp[now] += sum) %= mod;(ans += as[i] * sum % mod) %= mod;}write(ans);ent;Blue_Archive;
}T4:Baby Doll
看不懂，结论题，贺题解贺出来 10 pts，然后就不会了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 5e7 + 7;
constexpr int INF = 1e18;int n;
int m;
int q;
int mod;
int ans;
int a[N];
int fac[N];inline int read()
{int x = 0;char c = getchar_unlocked();for(;!isdigit(c);c = getchar_unlocked());for(;isdigit(c);x = x * 10 + c - 48,c = getchar_unlocked());return x;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{int res = 1;while(b){if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();mod = read();q = read();a[0] = fac[0] = 1;for(int i = 1;i <= n + m;i ++) a[i] = ((1 - qpow(q,i)) * qpow(1 - q,mod - 2) % mod + mod) % mod;for(int i = 1;i <= n + m;i ++) fac[i] = fac[i - 1] * a[i] % mod;ans = fac[n + m] * qpow(fac[n],mod - 2) % mod * qpow(fac[m],mod - 2) % mod;write(ans);ent;Blue_Archive;
}