T1 Idiot 的乘幂
题目大意就是给\(a,b,c,d,p\)满足
求解
这题考场一开始发现\(\gcd(a,c)=1\)没啥用，后来发现其实很巧妙，直接辗转相除\(a,c\)同时维护\(\chi^a,\chi^c\)最后剩下来的就是\(\chi\)
当然题解给了一个鬼才想到的做法构造\(\chi =\chi^1=\chi^{ax+cy}\)
所以可以用exgcd求解方程
\[ax+cy=1 \]然后直接用\(\chi=b^xd^y\)求解就行了。
#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
LL fpow(LL a,LL b,LL P){LL ret=1;
for(;b;b>>=1,a=a*a%P)
if(b&1)ret=ret*a%P;
return ret;
}
LL exgcd(LL a,LL b,LL &x,LL &y){
if(b==0)return x=1,y=0,a;
LL d=exgcd(b,a%b,y,x);
return y=y-a/b*x,d;
}
LL inv(LL x,LL P){
LL ret,kth;
exgcd(x,P,ret,kth);
return (ret%P+P)%P;
}
LL solve(LL a,LL b,LL ib,LL c,LL d,LL id,LL P){
if(c==0)return b;
return solve(c,d,id,a%c,b*fpow(id,a/c,P)%P,ib*fpow(d,a/c,P)%P,P);
}
int main(){
int T;scanf("%lld",&T);
while(T--){
LL a,b,c,d,P;
scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&P);
if(fpow(b,c,P)!=fpow(d,a,P)){
puts("No Solution!");continue;}
LL ans=solve(a,b,inv(b,P),c,d,inv(d,P),P);
if(fpow(ans,a,P)==b&&fpow(ans,c,P)==d)
printf("%lld\n",ans);
else puts("No Solution!");
}
return 0;
}
T2 小 D 与原题
大意说构造\(n-1\)组，每组\(\frac n 2\)个点对，使得每组里用的数不同，\(n-1\)组里使用的所有点对不相同
这个题一眼淼题，再看一眼就会爆炸发现不简单，他要求每次\(\frac n2\)题使用的原题不能相同，当然在一小时思考后想出了正解。
考虑把点从\(0\)到\(n-1\)标号，我们使第\(x+1\)组匹配包含满足\(i+j\equiv x(\mod n-1)\)的边\((i,j)\)和一条边\((p,n-1)\)满足\(2p\equiv x(\mod n-1)\)就可以了，正确性可以保证
#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
const int N=1005;
int n;
bool flag[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++,putchar(10))
for(int j=1;j<n;j++){
int k=(n-1-j+i)%(n-1)+1;
if(k==j)k=n;
if(j!=k&&!flag[j][k]){
printf("%d %d ",j,k);
flag[j][k]=flag[k][j]=1;
}
}
return 0;
}
T3 小 D 与随机
大意说给一棵树，定义好点为一个点权值是这个点到根的链上所有节点权值的最大值，每个节点的权值为1到n，且两两不同，好点个数为\(c\)，求\(k^c\)的总和
考场，考虑水分，观察到有\(40\%\)的链，直接dp，这里很滑稽，20分暴力不会写写了个40分的链。
设状态\(f_i\)表示前\(i\)个答案的总和，因为如果第\(i\)个点是好点那么对于前\(i\)个节点来说它只有一种选法，如果\(i\)个点不是好点的话它不能选最大的所以有\(i-1\)种选法，可得转移
\[f_i=kf_{i-1}+(i-1)f_{i-1} \]那么现在考虑正解，我们把树上的好点染成黑点，其他为白点
设\(f_{i,j}\)为以\(i\)为根的子树中有\(j\)个黑点的期望，先用树形背包转移出在\(i\)子树中不计\(i\)节点的\(f\)值。
然后分类讨论
- 若\(i\)节点为黑点那么，显然的概率为\(\frac 1{j+1}\)有转移\(F_j=F_j+\frac{kf_{i,j}}{j+1}\)
- 若\(i\)节点为白点，我们可以容斥一波，先加上当前点随便黑白的期望，再减去当前节点为黑点的期望，发现\(F_j=F_j+f_{i,j}-f_{i,j-1}\)
综合一下转移即可
#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
const int N=5005;
const LL mod=998244353;
LL fac[N+5],inv[N+5];
LL fpow(LL a,LL b){LL ret=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1)ret=ret*a%mod;
return ret;
}
void init(){fac[0]=1;
for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
inv[N]=fpow(fac[N],mod-2);
for(int i=N;i;i--)inv[i-1]=inv[i]*i%mod;
}
LL Inv(LL x){return inv[x]*fac[x-1]%mod;}
struct Edge{int Nxt,To;}Ed[N<<1];
int Head[N],Cnt;
void Add(int u,int v){
Ed[++Cnt]={Head[u],v};
Head[u]=Cnt;
}
LL f[N][N],F[N],K;
int sze[N];
void add(LL &x,LL y){x=(x+y+mod)%mod;}
void Dfs(int u,int fa){
f[u][0]=1;
for(int i=Head[u],v;i;i=Ed[i].Nxt)
if((v=Ed[i].To)!=fa){
Dfs(v,u);
for(int j=0;j<=sze[u];j++)
for(int k=0;k<=sze[v];k++)
add(F[j+k],f[u][j]*f[v][k]%mod);
sze[u]+=sze[v];
for(int j=0;j<=sze[u];j++)
f[u][j]=F[j],F[j]=0;
}
for(int i=0;i<=sze[u];i++){
add(F[i+1],f[u][i]*K%mod*Inv(i+1)%mod);
if(fa)add(F[i],f[u][i]),add(F[i+1],-f[u][i]);
}
sze[u]++;
for(int i=0;i<=sze[u];i++)f[u][i]=F[i],F[i]=0;
}
int main(){
init();
int n;
scanf("%d%lld",&n,&K);
for(int i=1,u,v;i<n;i++)
scanf("%d%d",&u,&v),Add(u,v),Add(v,u);
Dfs(1,0);
LL ans=0;
for(int i=1;i<=n;i++)add(ans,f[1][i]);
printf("%lld",ans*fac[n]%mod);
return 0;
}
T4 小 D 与游戏
这题考场没交，没啥想法。
题目大意是说一个由a,b,c组成的字符串，每次可以选两个相邻且不同的字符，把这两个字符改成另外一个字符
直接上正解，该题有以下结论
- 首先考虑把a,b,c分别设为0,1,2，那么会发现每次修改，字符串的每位之和前后是相同的
- 然后是最终串必然至少有两个相邻的相同字符（除非初始串相邻两两不同然后不操作）
- 最后是只要满足以上两条的字符串都可以构造出来（最为离谱，不会证）
这题的三个结论对于\(|S|\le 3\)不适用，所以可以打表
最后特判一下初始相邻两两不同的情况，答案++，和字符全相同直接输出1即可
#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL mod=998244353;
char ch[N];
int a[N];
LL f[N][3][3][2];
LL add(LL &x,LL y){x+=y,x%=mod;}
int main(){fre(game);
cin>>ch+1;
int n=strlen(ch+1),m=0;
for(int i=1;i<=n;i++)
a[i]=ch[i]-'a',m+=a[i],m%=3;
if(n==1)return puts("1"),0;
if(n==2)return puts(a[1]==a[2]?"1":"2"),0;
if(n==3){
if(a[1]==a[2]&&a[2]==a[3])puts("1");
else if(a[1]==a[2]||a[2]==a[3])puts("6");
else if(a[1]==a[3])puts("7");
else puts("3");
return 0;
}
f[1][0][0][0]=f[1][1][1][0]=f[1][2][2][0]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<=2;j++)
for(int k=0;k<=2;k++)
for(int w=0;w<=2;w++){
if(j!=k||i==1)
add(f[i][j][(w+j)%3][1],f[i-1][k][w][1]),
add(f[i][j][(w+j)%3][0],f[i-1][k][w][0]);
else
add(f[i][j][(w+j)%3][1],f[i-1][k][w][1]),
add(f[i][j][(w+j)%3][1],f[i-1][k][w][0]);
}
LL ans=0;bool flag1=1,flag2=1;
for(int i=1;i<n;i++)if(a[i]!=a[i+1]){flag1=0;break;}
for(int i=1;i<n;i++)if(a[i]==a[i+1]){flag2=0;break;}
for(int i=0;i<=2;i++)ans=(ans+f[n][i][m][1])%mod;
printf("%lld",flag1?1:(ans+flag2));
return 0;
}