题解是我“氪金”弄来的，勿外传。。否则会被官方封号的
注意：Div1的同学是CDEF四道题目，Div2的同学是ABCD四道题目。
A题：可持久化动态仙人掌的直径问题（雾）
题解思路：
本题代码（简单到爆，，，所以叫签到题）
#include<bits/stdc++.h>
int n,m;
int main(){
scanf("%d%d",&n,&m);
printf("%d",(int)(pow(n,1.0/m)+1e-12));
return 0;
}Continue to next page....
B题：混凝土数学
题解思路：
本题代码：
#include<bits/stdc++.h>
using namespace std;
#define FL(a) {freopen(a".in","r",stdin);freopen(a".out","w",stdout);}
#define Mod 998244353
#define int long long
const int mx=200000;
int n,a,tax[200005],sum[200005];
const int inv2=(Mod+1)/2,inv3=(Mod+1)/3,inv6=inv2*inv3%Mod;
signed main(){
// FL("data1-1");
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a);
tax[a]++;
}
int ans=0;
for(int i=1;i<=mx;++i)sum[i]=(sum[i-1]+tax[i])%Mod;
for(int i=1;i<=mx;++i){
int N=tax[i];
if(N<2)continue;
// cerr<<"N: "<<N<<endl;
ans=(ans+N*(N-1)/2%Mod*(sum[min(i*2-1,mx)]-N)%Mod+N*(N-1)%Mod*(N-2)%Mod*inv6%Mod)%Mod;
}
printf("%lld\n",ans);
cerr<<"ans: "<<ans<<endl;
return 0;
}
C题：论如何玩转 Excel 表格
思路：
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
const int maxn = 2e6+10;
int read(){
int x=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
return x*f;
}
int k,m,n;
int a[maxn],b[maxn],c[maxn],d[maxn],fa[maxn],p[maxn];
pair<int,int> P[maxn];
int sum[maxn];
void add(int x){for(int i=x;i<=n;i+=i&-i)sum[i]++;}
int query(int x){int SUM=0;for(int i=x;i;i-=i&-i)SUM+=sum[i];return SUM;}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++){c[i]=read();P[c[i]]=make_pair(i,1);}
for(int i=1;i<=n;i++){d[i]=read();P[d[i]]=make_pair(i,2);}
for(int i=1;i<=n;i++){fa[a[i]]=b[i];fa[b[i]]=a[i];}
for(int i=1;i<=n;i++){
if(fa[c[i]]!=d[i] || fa[d[i]]!=c[i]){puts("dldsgay!!1");return 0;}
if((P[a[i]].first+P[a[i]].second)%2!=(i+1)%2){puts("dldsgay!!1");return 0;}
if((P[b[i]].first+P[b[i]].second)%2!=(i+2)%2){puts("dldsgay!!1");return 0;}
}
for(int i=1;i<=n;i++)p[a[i]]=i;
for(int i=1;i<=n;i++)c[i]=p[c[i]]+p[d[i]];
long long ans=0;
for(int i=n;i>=1;i--){
ans+=query(c[i]);
add(c[i]);
}
printf("%lld\n",ans);
return 0;
}D题：可重集
思路：
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT __int128
#define ULL unsigned long long
int read(){
int a=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while('0'<=c&&c<='9'){
a=a*10+c-48;
c=getchar();
}
return a;
}
int MUL(int a,int x,int Mod){
// return (INT)a*x%Mod;
int ans=0,w=a;
while(x){
if(x&1)ans=(ans+w)%Mod;
w=(w+w)%Mod;
x>>=1;
}
return ans;
}
const int G1=1145141;
const int MMod=1000000000000000003ll;
#define MN 2000005
#define Ls (x<<1)
#define Rs (x<<1|1)
#define mid ((l+r)>>1)
#define piii pair<int,int>
#define mp make_pair
#define x first
#define y second
int aupd(int a){return (a<MMod)?a:(a-MMod);}
int supd(int a){return (a>=0)?a:(a+MMod);}
int pw1[MN],s1[MN];
int sum[MN];
int n,q,a[MN];
void build(){
for(int i=1;i<=n;++i){
s1[i]=aupd(s1[i]+pw1[a[i]]);
sum[i]=sum[i]+a[i];
int to=i+(i&(-i));
s1[to]=aupd(s1[to]+s1[i]);
sum[to]=sum[to]+sum[i];
}
}
void add(int x,int v1,int v2){
while(x<=n){
s1[x]=aupd(s1[x]+v1);
sum[x]+=v2;x+=x&(-x);
}
}
piii ask(int x){
piii res=mp(0,0);
while(x){
res.x=aupd(res.x+s1[x]);
res.y+=sum[x];
x-=x&(-x);
}
return res;
}
piii qry(int l,int r){
piii R=ask(r),L=ask(l-1);
R.x=supd(R.x-L.x);
R.y-=L.y;
return R;
}
signed main(){
n=read();q=read();
pw1[0]=1;
for(int i=1;i<=1000000;++i){
pw1[i]=MUL(pw1[i-1],G1,MMod);
}
for(int i=1;i<=n;++i){
a[i]=read();
}
build();
for(int i=1;i<=q;++i){
int op=read();
if(!op){
int x=read(),y=read();
add(x,supd(pw1[y]-pw1[a[x]]),y-a[x]);
a[x]=y;
}
else{
int l1=read(),r1=read(),l2=read(),r2=read(),len=r1-l1+1;
piii res1=qry(l1,r1),res2=qry(l2,r2);
int k=res2.y-res1.y;
if(abs(k)%len!=0){puts("NO");continue;}
k/=len;
if(k>=0){
res1.x=MUL(res1.x,pw1[k],MMod);
}
else {
k=-k;
res2.x=MUL(res2.x,pw1[k],MMod);
}
if(res1.x==res2.x)puts("YES");
else puts("NO");
}
}
return 0;
}
E题：序列
思路：
代码：
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline T read(){
T f=0,x=0;char c=getchar();
while(!isdigit(c)) f=c=='-',c=getchar();
while(isdigit(c)) x=x*10+c-48,c=getchar();
return f?-x:x;
}
namespace run{
const int N=5009,mod=998244353;
inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}
inline int sub(int x,int y){return x>=y?x-y:x+mod-y;}
inline int qpow(int x,int y){
int ret=1;
while(y){
if(y&1) ret=1LL*x*ret%mod;
x=1LL*x*x%mod,y>>=1;
}
return ret;
}
int fac[N],ifac[N];
inline int C(int n,int m){
if(n<0 || m<0 || n<m) return 0;
return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}inline int calc(int n,int d,int m){return sub(C(n,n-d-m),C(n,n-d-m+1));}
int f[N][N],n,k,inv;
int main(){
n=read<int>(),k=read<int>(),inv=qpow(n,mod-2);
fac[0]=ifac[0]=ifac[1]=1;
for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=1;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
assert(1LL*fac[n-1]*ifac[n-1]%mod==1);
f[0][0]=1;
for(int i=1;i<=k;i++){
int sum=f[i-1][n];
for(int j=min(n,i);j;j--){
sum=(1LL*sum*j%mod*inv+f[i-1][j-1])%mod;
f[i][j]=1LL*inv*(n-j+1)%mod*sum%mod;
}
}
int chk=0;
for(int i=0;i<=n;i++) chk=add(chk,f[k][i]);
assert(chk==1);
for(int i=1;i<=n;i++) f[k][i]=1LL*f[k][i]*qpow(C(n,i),mod-2)%mod;
int ans=0;
for(int i=1;i<=n;i++)
for(int j=2;j<=n && min(i,n-i)>=j/2;j+=2)
ans=(1LL*f[k][i]*calc(n,i,(j-2*i)/2)%mod*j+ans)%mod;
printf("%d\n",ans);
return 0;
}
}
int main(){
#ifdef my
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
#endif
return run::main();
}F题：一次函数
思路：
代码：
#include <bits/stdc++.h>
using namespace std;
const int Maxi = 1030, Maxn = 20005;
int n, m, ct, bloc, f[Maxn][Maxi], pos[Maxi], fac[Maxi];
pair <int, int> from[Maxn][Maxi];
long long d, p, goal, val[Maxn], arr[Maxn];
pair <int, long long> ans[Maxn];
map <int, int> Ma;
typedef pair <long long, long long> pll;
pll G;
pll operator * (const pll &x, const pll &y)
{
return make_pair((x.first * y.second + x.second * y.first) % p, x.second * y.second % p);
}
long long gcd(long long x, long long y)
{
return x == 0 ? y : gcd(y % x, x);
}
long long fast_pow(long long x, long long y)
{
long long ans = 1, now = x;
while (y)
{
if (y & 1) ans = ans * now % p;
now = now * now % p;
y >>= 1;
}
return ans;
}
pll fast_pow(pll x, long long y)
{
pll ans = make_pair(0, 1), now = x;
while (y)
{
if (y & 1) ans = ans * now;
now = now * now;
y >>= 1;
}
return ans;
}
void dp(void)
{
int maxi = (1 << ct) - 1;
memset(f, 0x3f, sizeof(f));
f[0][maxi] = 0;
for (int i = 1; i <= n; i++)
{
int sta = 0;
long long tmp_val = val[i] / gcd(val[i], goal);
for (int j = 1; j <= ct; j++)
if (tmp_val % fac[j] == 0) sta |= 1 << (j - 1);
for (int j = 1; j <= maxi; j++)
if (f[pos[j]][j] + 1 < f[pos[j & sta]][j & sta])
{
pos[j & sta] = i;
f[i][j & sta] = f[pos[j]][j] + 1;
from[i][j & sta] = make_pair(pos[j], j);
}
}
}
int get_unit(void)
{
int maxi = sqrt(p - 1);
for (int i = 2; ; i++)
{
for (int j = 2; j <= maxi; j++)
if ((p - 1) % j == 0)
{
if (fast_pow(i, j) == 1) goto END;
if (fast_pow(i, (p - 1) / j) == 1) goto END;
}
return i;
END:;
}
}
void get_factor(void)
{
int maxi = sqrt(p - 1), tmp = p - 1;
for (int i = 2; i <= maxi; i++)
if (tmp % i == 0)
{
fac[++ct] = i;
while (tmp % i == 0) tmp /= i;
}
if (tmp != 1) fac[++ct] = tmp;
fac[++ct] = p;
}
pll exgcd(long long x, long long y)
{
if (!x)
return make_pair(0, 1);
else
{
pll tmp = exgcd(y % x, x);
return make_pair(tmp.second - tmp.first * (y / x), tmp.first);
}
}
long long mod(__int128 x)
{
return (x % (p * (p - 1)) + (p * (p - 1))) % (p * (p - 1));
}
void work(int lt, long long goal_now)
{
long long g = p * (p - 1), div = gcd(goal_now, p * (p - 1));
for (int i = lt + 1; i <= m; i++)
g = gcd(g, arr[i]);
div = gcd(g, arr[lt]);
arr[lt] /= div, g /= div, goal_now /= div;
pll result = exgcd(arr[lt], g);
ans[lt].second = mod((__int128) result.first * goal_now);
if (lt == m - 1)
{
ans[m].second = mod((__int128) result.second * goal_now);
return ;
}
work(lt + 1, mod(mod((__int128) result.second * goal_now) * (__int128) g));
}
void BSGS_init(void)
{
bloc = sqrt(n * p);
long long now = 1;
d = get_unit();
for (int i = 0; i < bloc; i++)
{
Ma[now] = i;
now = now * d % p;
}
}
long long BSGS(pll val_now)
{
long long inv = fast_pow(fast_pow(d, bloc), p - 2), now_inv = 1;
for (int j = 0; j < p / bloc + 1; j++)
{
if (Ma[now_inv * val_now.second % p])
{
long long tmp = Ma[now_inv * val_now.second % p] + j * (long long) bloc;
pll tmp_val = val_now * fast_pow(make_pair(1, d), p * (p - 1) - tmp);
return ((p - 1) * (p - tmp_val.first * d % p) + tmp) % (p * (p - 1));
}
(now_inv *= inv) %= p;
}
}
int main()
{
scanf("%d%lld%lld%lld", &n, &p, &G.first, &G.second);
BSGS_init();
get_factor();
goal = BSGS(G);
long long g = gcd(p * (p - 1), goal);
for (int i = 1; i <= n; i++)
{
pll x;
scanf("%lld%lld", &x.first, &x.second);
val[i] = BSGS(x), g = gcd(g, val[i]);
}
for (int i = 1; i <= n; i++) val[i] /= g;
dp();
if (f[pos[0]][0] > n)
{
puts("-1");
return 0;
}
pair <int, int> now = make_pair(pos[0], 0);
while (now.first)
{
arr[++m] = val[now.first];
ans[m].first = now.first;
now = from[now.first][now.second];
}
work(1, goal);
printf("%d\n", m);
for (int i = 1; i <= m; i++)
printf("%d %lld\n", ans[i].first, ans[i].second);
return 0;
}希望对大家有所帮助。