本人只做出了前四题，所以只写前四题的题解
A<mtext> </mtext>数数\mathcal{A\ 数数}A 数数
Description\mathcal{Description}Description
给出 nnn，求
<mstyle displaystyle="true" scriptlevel="0"><munderover>∑i=1n</munderover> <munderover>∑j=1n</munderover>i×j</mstyle>\begin{aligned}\sum_{i=1}^n\sum_{j=1}^ni\times j\end{aligned}i=1∑nj=1∑ni×j 和 <mstyle displaystyle="true" scriptlevel="0"><munderover>∏i=1n</munderover> <munderover>∏j=1n</munderover>i×j</mstyle>\begin{aligned}\prod_{i=1}^n\prod_{j=1}^ni\times j\end{aligned}i=1∏nj=1∏ni×j
答案对 998244353998244353998244353取模
Solution\mathcal{Solution}Solution
这是一道送分题
<mstyle displaystyle="true" scriptlevel="0"><munderover>∑i=1n</munderover> <munderover>∑j=1n</munderover>i×j=<munderover>∑i=1n</munderover>i×(<munderover>∑j=1n</munderover>j)=(<munderover>∑j=1n</munderover>j)×(<munderover>∑i=1n</munderover>i)=(n(n+1)2)2</mstyle>\begin{aligned}\sum_{i=1}^n\sum_{j=1}^ni\times j=\sum_{i=1}^ni\times\left(\sum_{j=1}^nj\right)=\left(\sum_{j=1}^nj\right)\times\left(\sum_{i=1}^ni\right)=\left(\frac{n(n+1)}{2}\right)^2\end{aligned}i=1∑nj=1∑ni×j=i=1∑ni×(j=1∑nj)=(j=1∑nj)×(i=1∑ni)=(2n(n+1))2
这个做多了题目就是一眼的事了
它的几何性质是一个 n×nn\times nn×n的矩阵其所有子矩阵个数
<mstyle displaystyle="true" scriptlevel="0"><munderover>∏i=1n</munderover> <munderover>∏j=1n</munderover>i×j=<munderover>∏i=1n</munderover>in<munderover>∏j=1n</munderover>j=(<munderover>∏j=1n</munderover>j)n<munderover>∏i=1n</munderover>in=(<munderover>∏j=1n</munderover>jn)<munderover>∏i=1n</munderover>in=<munderover>∏i=1n</munderover>i2n=(<munderover>∏i=1n</munderover>i)2n</mstyle>\begin{aligned}\prod_{i=1}^n\prod_{j=1}^ni\times j=\prod_{i=1}^ni^n\prod_{j=1}^nj = \left(\prod_{j=1}^nj\right)^n\prod_{i=1}^ni^n = \left(\prod_{j=1}^nj^n\right)\prod_{i=1}^ni^n = \prod_{i=1}^ni^{2n}=\left(\prod_{i=1}^ni\right)^{2n}\end{aligned}i=1∏nj=1∏ni×j=i=1∏ninj=1∏nj=(j=1∏nj)ni=1∏nin=(j=1∏njn)i=1∏nin=i=1∏ni2n=(i=1∏ni)2n
不会推式子怎么办！
和博主一样直接看吧！
第一个就不说了
第二个反正都是乘，我们直接考虑有多少个被乘了不就可以了吗
考虑 iii被乘的次数，在形如 i×ji\times ji×j这样的情况每个都有 iii，共有 n+1n+1n+1个 iii ( i×ii\times ii×i这样的情况有两个 iii)
形如 j×i(j!=i)j \times i(j!=i)j×i(j!=i)的情况对于每个 jjj都会有，共有 n−1n-1n−1个，所以 iii会被乘 2n2n2n次
Code\mathcal{Code}Code
/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月14日 星期六 19时06分48秒 *******************************/ #include <cstdio> #include <fstream> #define ll long long using namespace std; const int maxn = 10000005; const int mod = 998244353; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} int T,n,ans1,ans2; int s[maxn],mi[maxn]; //{{{ksm int ksm (int a,int b) { int s=1; for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) s=1ll*s*a%mod; return s; } //}}} int main() { s[1]=1; for (int i=2;i<=maxn-5;++i) s[i]=1ll*s[i-1]*i%mod; cin>>T; while (T--){ cin>>n; ans1=1ll*n*(n+1)/2%mod; ans1=1ll*ans1*ans1%mod; ans2=ksm(s[n],2*n)%mod; printf("%d %d\n",ans1,ans2); } return 0; }
B<mtext> </mtext>Galahad\mathcal{B\ Galahad}B Galahad
Description\mathcal{Description}Description
魔女要测试骑士的能力，要求他维护一个长度为 nnn的序列，每次要询问一个区间的和。
但是魔女觉得太简单了，骑士能轻松记住 nnn个数的前缀和。
于是，魔女要求他回答一个区间的和，但如果某一个数在这个区间出现了多次，这个数只能被计算一次。
n,m≤500000,1≤ai≤500000n,m\leq 500000,1\leq a_i\leq 500000n,m≤500000,1≤ai≤500000
Solution\mathcal{Solution}Solution
这题好像是曾经的莫队板子题，但是开大了数据范围，于是咱的莫队就 TTT了
换个思路
先将查询按照 rrr从小到大排序
令 lastilast_ilasti表示数字 iii上一次的出现位置
当我们找到一个数 iii时，只要在当前位置加上 iii，在 lastilast_ilasti减去 iii即可保证不会重复计算
由于我们将查询按照 rrr从小到大排序了
所以每个当前查询一定经过现在这个位置
而 l≤lastil\leq last_il≤lasti的情况，我们已经将 lastilast_ilasti的答案抵消了，所以每个 iii只会被计算一次
而现在实际上就是要求一段区间的加和，这个用树状数组维护就可以了
Code\mathcal{Code}Code
/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月14日 星期六 19时18分27秒 *******************************/ #include <cstdio> #include <algorithm> #define ll long long using namespace std; const int maxn = 1000006; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} struct Q{ int l,r,id; }q[maxn]; int n,m; int a[maxn],last[maxn]; ll c[maxn],ans[maxn]; bool cmp(Q a,Q b){ return a.r<b.r;} //{{{query ll query(int x) { ll res=0; while(x>0){ res+=c[x];x-=x&-x;} return res; } //}}} //{{{insert void insert(int x,int v) { while(x<=n){ c[x]+=v;x+=x&-x;} } //}}} int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1,cmp); int t=1; for(int i=1;i<=n;i++){ if(last[a[i]]) insert(last[a[i]],-a[i]); insert(i,a[i]); while(i==q[t].r) ans[q[t].id]=query(q[t].r)-query(q[t].l-1),t++; last[a[i]]=i; } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }
C<mtext> </mtext>烹饪\mathcal{C\ 烹饪}C 烹饪
Description\mathcal{Description}Description
小 YYY上山拜师学艺，经过 101010年之长的厨艺练习，已成为当世名厨，今天他接受邀请，在众人面前展示自己高超的厨艺。
人们给小 YYY提供了 nnn种食物，每种食物无限量供应，每种食物都有一个美味值，记为 aia_iai。
小 YYY为了展示他的厨艺，他需要挑选出食材，使自己可以烹饪出任意正整数美味值的菜肴，初始时菜肴的美味值为 000，每次加入一种食材，他可以选择让菜肴的美味值上升 aia_iai，也可以选择让菜肴的美味值下降 aia_iai（或许最后会弄出来黑暗料理？）。
作为当世名厨，小 YYY自然知道该怎么挑选食材最佳。可是他并不知道有多少种最佳的挑选食材方案，于是他找到了你来帮忙。
我们使用无序数列 (b1,b2,…,bm)\left(b_1,b_2,\ldots,b_m\right)(b1,b2,…,bm)来表示从原来的 nnn种食材中挑选出了 mmm种食材，第 iii种食材编号为 bib_ibi的方案。同时你需要注意， (1,2)\left(1,2\right)(1,2)和 (2,1)\left(2,1\right)(2,1)为同一种方案，且当 i!=ji!=ji!=j时 bi!=bjb_i != b_jbi!=bj。
最佳的挑选食材方案指，挑选出 种食材 mmm种食材 (1≤m≤n)(1\leq m\leq n)(1≤m≤n)，让他们能够组合出任意正整数美味值的菜肴。
答案对 998244353998244353998244353取模。
Solution\mathcal{Solution}Solution
又是一个计数题
计数题有很多方法， dpdpdp，容斥，递推等都可以计数
最开始我打算按照一定方式不重不漏的组合开始计算
但是想了半天除了几个错误的方法仍然没什么思路
在想的时候发现按照一定方式不如直接算不合法的
于是考虑容斥
首先我们要知道一点
能组合出任意正整数 ⇔\Leftrightarrow⇔能组合出 111
所以我们将目标锁定在能否组合出 111
合法的方法=所有方法-不能组合出 111的方法
考虑哪些一定能组合出 111
最显然的是 (a,a+1)(a,a+1)(a,a+1)这样的是合法的
而如果 aaa是个合数，设 kkk为 aaa的一个因子
那么 (k,a+1)(k,a+1)(k,a+1)也是合法的
可以想到任意 a,ba,ba,b只要满足 ax−by=1ax-by=1ax−by=1就合法
只要这个式子有解就合法 ax+(−by)=1ax+(-by)=1ax+(−by)=1
而其有解条件是 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1
其实换个思路也可以得到
只要是互质的就可以满足条件，因为它们之间一个对另一个取模的剩余系是可以得到 111的
或者考虑只要是不互质的数就不可以满足条件，因为无论他们怎么加减，结果都会有他们的最大公约数在里面
于是可以知道，得要弄出这样的序列 a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an，其满足 gcd(a1,a2,…,an)=1gcd(a_1,a_2,\ldots,a_n)=1gcd(a1,a2,…,an)=1
求这样的数列个数就可以考虑容斥了
gcd=1gcd=1gcd=1的序列数 ===总序列数 −gcd<mtext> </mtext>!=1-gcd\ !=1−gcd !=1的序列数
考虑枚举它们的 gcdgcdgcd，令 f[i]f[i]f[i]表示以 iii作为 gcdgcdgcd的序列数，那么答案就是 f[1]f[1]f[1]
而 f[i]=gcdf[i]=gcdf[i]=gcd是 iii的倍数的序列数 −f[i∗2]−f[i∗3]−…−f[i∗k]-f[i*2]-f[i*3]-\ldots-f[i*k]−f[i∗2]−f[i∗3]−…−f[i∗k]
用 num[i]num[i]num[i]表示有多少个数是 iii的倍数
gcdgcdgcd是 iii的倍数的序列数= 2num[i]−12^{num[i]}-12num[i]−1
2num[i]−12^{num[i]}-12num[i]−1就是有 num[i]num[i]num[i]个数可选可不选，但必须至少选一个的方案数
这样这道题就得到解决了
Code\mathcal{Code}Code
/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月14日 星期六 19时33分10秒 *******************************/ #include <cstdio> #include <fstream> #include <algorithm> using namespace std; const int maxn = 3005; const int mx = 2000; const int mod = 998244353; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} int n; int a[maxn],num[maxn],f[maxn],s[maxn],mi[maxn]; void add (int &x,int y){ x=((x+y)%mod+mod)%mod;} //{{{gcd int gcd (int a,int b) { if (!b) return a; return gcd(b,a%b); } //}}} int main() { mi[0]=1; cin>>n; for (int i=1;i<=n;++i) cin>>a[i]; for (int i=1;i<=3000;++i) mi[i]=2ll*mi[i-1]%mod; for (int i=mx;i>=1;--i){ for (int j=1;j<=n;++j) if (a[j]%i==0) ++num[i]; f[i]=(mi[num[i]]+mod-1)%mod; for (int j=2;i*j<=mx;++j) add(f[i],-f[i*j]); } printf("%d\n",f[1]); return 0; }
D<mtext> </mtext>粉丝群\mathcal{D\ 粉丝群}D 丝群
Description\mathcal{Description}Description
在 wjyyywjyyywjyyy粉丝群中，除了 wjywjywjy一共有 nnn个人，编号为 111到 nnn。
大家准备一起膜爆 wjywjywjy，也就是说复读 2n2n2n次消息，并且由于这 nnn个人在膜 wjywjywjy上是统一的，所以每个人都必须至少复读一次。
wjywjywjy想要禁言掉一些人，但是这里是 wjywjywjy粉丝群，不能随便禁言膜 wjywjywjy的人，于是 wjywjywjy定下一个规则：
如果这 nnn个人，能够分成两组，使得两个组中所有人的复读次数的加和是相同的，那么这 nnn个人都要被禁言。
这 nnn个人开始讨论，他们不想被暴政。
那么问题来了，有多少种复读的分配方法，使得 wjyyywjyyywjyyy没法把这 nnn个人分成满足以上条件的两组？
然而 wjywjywjy的粉丝太多了，您只要输出分配方法的种数以及这些分配方法中字典序第 kkk小的分配方式的异或和即可。
注意：如果有两个人，则复读次数分别为 (1,3)(1,3)(1,3)与复读次数分别为 (3,1)(3,1)(3,1) 算两种不同的分配方式。
Solution\mathcal{Solution}Solution
这题打表找规律也可以看出来的
首先每人都至少复读一次，就先记每人都复读了一次
| 111 | 222 | 333 | …\ldots… | nnn |
|---|---|---|---|---|
| 111 | 111 | 111 | …\ldots… | 111 |
现在还剩 nnn次复读要分给这些人，并且要使它们无法分成两组复读次数加和是一样的
先考虑极端情况
若把这 nnn次机会再每人一次
那么最终就是每人复读两次
当 nnn为奇数时，这样是满足条件的，而 nnn为偶数是不满足的
若把这 nnn次机会全部给一个人，那么那个人就有 n+1n+1n+1次复读
剩下的人加起来也不会超过他的复读次数，所以全部给一个人也是满足条件的
再考虑普遍的情况
若有些人没有被分到复读次数（即只复读了一次）
我们把复读次数大于 111的人尽量平均分成两组，两组复读次数分别为 x,y(x<y)x,y(x<y)x,y(x<y)
那么一定有 y−xy-xy−x个人是只复读了一次的
这里可以自己手玩 3,4,5,63,4,5,63,4,5,6这样的看一看以便理解
把这些人放到 xxx那边去，就刚好两组平均了
所以这些都不满足条件
综上
只有把 nnn次复读全部给一个人是绝对满足的
当 nnn为奇数时所有人都复读两次也是可以的
而字典序肯定是 (1,1,…1,n+1),(1,1,…,n+1,1)…(n+1,1,…,1,1)(1,1,\ldots1,n+1),(1,1,\ldots,n+1,1)\ldots(n+1,1,\ldots,1,1)(1,1,…1,n+1),(1,1,…,n+1,1)…(n+1,1,…,1,1)这样子的
共有 nnn种满足条件，当 nnn为奇数时还要多一种 (2,2,…,2,2)(2,2,\ldots,2,2)(2,2,…,2,2)
前面一堆 111异或起来不是 111就是 000都是可以 O(1)O(1)O(1)判的
Code\mathcal{Code}Code
/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月14日 星期六 20时36分37秒 *******************************/ #include <cstdio> #include <fstream> #define ll long long using namespace std; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} ll n,k; int main() { cin>>n>>k; if (n==1){ printf("1\n2\n");return 0;} if (n&1) printf("%lld\n%lld\n",n+1,(k==n)?2:n+1); else printf("%lld\n%lld\n",n,(n+1)^1); return 0; }
如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
京公网安备 11010502036488号