A. 猜拳游戏
可以分成两部分解决
一部分解决每一轮赢的概率，一部分解决最后获胜的概率
先看第一部分，发现每一轮平局不影响结果，于是忽略他，只考虑输赢的情况
设 \(p,r\) 分别为原来赢和输的概率，设 \(q=\frac{p}{p+r}\) 即现在每轮赢的概率
变化一下形式 \(\frac{p}{p+r}=1-\frac{r}{p+r}=1-\frac{1}{1+\frac{p}{r}}\)
于是最大化 \(\frac{p}{r}\) 即可,可以使用分数规划
二分一个 \(mid\) 和当前的 \(\frac{p}{r}\) 比较
\(\frac{p}{r}>mid \rightarrow p>mid\times r \rightarrow p-mid\times r>0\)
于是假设 \(A\) 赢一轮 \(+1\) 分 \(B\) 赢一轮 \(-mid\) 分
从后往前 \(dp\) ,设 \(f_{i,j}\) 表示第 \(i\) 轮赢比输多 \(j\) 局的最大 \(p-mid\times r\)
然后一下看 \(f_{0,0}\) 是否大于 \(0\)
\(f_{n,x}\) 边界
-
\(x>0\) 为 \(1\)
-
\(x<0\) 为 \(-mid\)
-
\(x=0\) 为 \(0\)
再看第二部分，发现 \(m1+m2\) 的数量级很小于是直接高斯消元
\(a_i\) 表示多赢 \(i\) 轮的概率 \(a_i=a_{i-1}\times q+a_{i+1}\times (1-q)\)
注意一下边界
Code
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define eps 1e-8
#define O 1000
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m1,m2;
double a[1010][3],f[1010][2010],q;
inline bool check(double mid){
double r1,r2,r3;
memset(f,0,sizeof(f));
for(int i=-n;i<=n;i++){if(i>0) f[n][i+O]=1;if(i==0) f[n][i+O]=0;if(i<0) f[n][i+O]=-mid;}
for(int i=n;i;i--) for(int j=-i+1;j<=i-1;j++){
r1=f[i][j+1+O]*a[i][1]+f[i][j+O]*a[i][0]+f[i][j-1+O]*a[i][2];//+a[i][1]-mid*a[i][2];
r2=f[i][j+1+O]*a[i][2]+f[i][j+O]*a[i][1]+f[i][j-1+O]*a[i][0];//+a[i][2]-mid*a[i][0];
r3=f[i][j+1+O]*a[i][0]+f[i][j+O]*a[i][2]+f[i][j-1+O]*a[i][1];//+a[i][0]-mid*a[i][1];
f[i-1][j+O]=max({r1,r2,r3});
}
return f[0][0+O]>0;
}
namespace G{
double mp[210][210];//+m2
inline void gaussbuild(){
memset(mp,0,sizeof(mp));
for(int i=1;i<=m1+m2+1;i++) mp[i][i]=1;
for(int i=1;i<m1+m2;i++) mp[i][i+1]=-(1-q);
for(int i=3;i<=m1+m2+1;i++) mp[i][i-1]=-q;
mp[m2+1][m1+m2+2]+=1;
}
inline double gauss(int n){
int maxp;double div,mx;
for(int i=1;i<=n;i++){
maxp=i,mx=mp[i][i];
for(int j=i+1;j<=n;j++) if(fabs(mp[j][i])>mx) maxp=j,mx=fabs(mp[j][i]);
if(i!=maxp) swap(mp[i],mp[maxp]);
div=mp[i][i];
for(int j=1;j<=n+1;j++) mp[i][j]/=div;
for(int j=1;j<=n;j++){
if(i==j) continue;
if(mp[j][i]==0) continue;
div=mp[j][i]/mp[i][i];
for(int k=1;k<=n+1;k++) mp[j][k]=mp[j][k]-div*mp[i][k];
}
}
return mp[n][n+1];
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
while(1){
n=read(),m1=read(),m2=read();if(!n) break;
for(int i=1;i<=n;i++) a[i][0]=read()/100.0,a[i][2]=read()/100.0,a[i][1]=read()/100.0;
double l=0,r=10000;
while(r-l>eps){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
if(fabs(10000-l)<eps) q=1.00000;
else q=1.0-1.0/(l+1.0);
G::gaussbuild();
printf("%.5lf\n",G::gauss(m1+m2+1));
}
return 0;
}
B. B君的回忆
取 \(mod\) 意义下一定存在循环节，于是直接打表找规律
得出如下规律
将 \(p\) 分解为 \(\prod\limits_{i=1}^{cnt}pri_i^{c_i}\) 的形式
于是他的循环节长度为 \(\prod\limits_{i=1}^{cnt}f(pri_i)\times pri_i^{c_i-1}\)
\(f(x)\) 表示 \(\mod x\) 意义下循环节的长度
对于每个 \(f(x)\) 可以直接用矩阵 \(bsgs\) 求
每个 \(g(n)\) 都可以变成 \(a^xc\) 的形式（ \(a,c\) 均为矩阵 ）
于是套 \(bsgs\) 的板子 \(a^x\equiv b(\mod p)\) 稍微变化一下就能求 \(a^xc\equiv b(\mod p)\) 了
最后把答案都乘起来，对于每一层都求一遍就行
Code
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int T,a,b,n,k,mod;
int tmod[110];
map<int,int>AAA;
struct mat{
int a[4][4];
inline mat operator*(mat const &b)const{
mat c;memset(c.a,0,sizeof(c.a));
for(int i=1;i<=2;i++) for(int k=1;k<=2;k++) for(int j=1;j<=2;j++) (c.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
return c;
}
inline bool operator<(const mat &b)const{for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) if(a[i][j]!=b.a[i][j]) return a[i][j]<b.a[i][j];return false;}
inline bool operator==(const mat &b)const{for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) if(a[i][j]!=b.a[i][j]) return false;return true;}
inline bool empty(){for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) if(a[i][j]) return false;return true;}
inline void print(){for(int i=1;i<=2;i++,puts("")) for(int j=1;j<=2;j++) printf("%lld ",a[i][j]);}
}A,B;
inline mat qpow(mat x,int k){
mat res,base=x;for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) res.a[i][j]=(i==j);
while(k){if(k&1) res=res*base;base=base*base;k>>=1;}
return res;
}
inline int g(int x){
if(x==1) return b;if(x==0) return a;
memset(B.a,0,sizeof(B.a));
memset(A.a,0,sizeof(A.a));
B.a[1][1]=b;B.a[2][1]=a;
A.a[1][1]=3,A.a[1][2]=mod-1;
A.a[2][1]=1,A.a[2][2]=0;
A=qpow(A,x-1);B=A*B;
return B.a[1][1];
}
namespace MODDDD{
int prime[100],c[100],cnt,res;
map<mat,int> mp;
inline int bsgs(mat a,mat b,mat c,int p){
if((qpow(a,p)*c)==b) return p;
if((qpow(a,p-1)*c)==b) return p-1;
if((qpow(a,p+1)*c)==b) return p+1;
mp.clear();int t=sqrt(p)+1;mat w;memset(w.a,0,sizeof(w.a));for(int i=1;i<=2;i++) w.a[i][i]=1;
for(int i=0;i<=t;i++,w=w*a) mp[w*b]=i;
a=qpow(a,t);
if(a.empty()) return (b.empty())?1:-1;
memset(w.a,0,sizeof(w.a));for(int i=1;i<=2;i++) w.a[i][i]=1;
for(int i=0,j;i<=t;i++,w=w*a){
j=mp.find(w*c)==mp.end()?-1:mp[w*c];
if(j>=0&&i*t-j>0) return i*t-j;
}
return -1;
}
inline int getP(int pri){
mod=pri;
memset(B.a,0,sizeof(B.a));
memset(A.a,0,sizeof(A.a));
B.a[1][1]=1;B.a[2][1]=0;
A.a[1][1]=3,A.a[1][2]=mod-1;
A.a[2][1]=1,A.a[2][2]=0;
return bsgs(A,B,B,mod);
}
int gcd(int x,int y){return (!y)?x:gcd(y,x%y);}
inline int getmod(int p){
if(AAA.find(p)!=AAA.end()) return AAA[p];
int xxxx=p;
cnt=0;res=1;
for(int i=2;i*i<=p;i++) if(p%i==0){
prime[++cnt]=i;c[cnt]=0;
while(p%i==0) p/=i,c[cnt]++;
}
if(p>1) prime[++cnt]=p,c[cnt]=1;
for(int i=1,gg,cc;i<=cnt;i++){
cc=getP(prime[i]);
cc=(cc==-1?prime[i]:cc);
for(int j=1;j<c[i];j++) cc=cc*prime[i];
gg=gcd(res,cc);
res=res*cc/gg;
}
return AAA[xxxx]=res;
}
}
int F(int n,int k){
if(k==0) return n;
mod=tmod[k];
return F(g(n),k-1);
}
inline void solve(){
a=read(),b=read(),n=read(),k=read(),mod=read();
tmod[1]=mod;for(int i=2;i<=k;i++) tmod[i]=mod=MODDDD::getmod(mod);
printf("%lld\n",F(n,k));
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
T=read();while(T--) solve();
return 0;
}
C. 小 H 爱染色
要求 \(\sum\limits_{i=0}^{n-1}F(i)\times H(n-i)\)
球的编号从 \(0\) 到 \(n-1\)
\(F(x)\) 为给定不超过 \(m\) 次的多项式
\(H(i)\) 为给 \(i\) 个球染色其中第一个球必须染
朴素的式子为 \(H(i)=2\binom{i}{m-1}\binom{i}{m}+\binom{i}{m-1}^2\) 没啥拓展性
再看上面的式子 \(\sum\limits_{i=0}^{n-1}F(i)\times H(n-i)\)
可以对于每个 \(j\) 求出答案于是变成，为了方便把 \(n-1\) 变成 \(n\)
\(\sum\limits_{j=0}^mf_j\sum\limits_{i=0}^nH(n-i)i^j\)
考虑 \(i^j\) 的组合意义
\(i\) 个球染色一次染一个一共染 \(j\) 次
于是可以把两个式子化在一起，直接枚举两部分各染了几个球分别记录为 \(t,k\) ，这样就不需要枚举 \(i\) 了因为第 \(i\) 个球是后 \(k\) 个里的第一个所以一定被染了
后面的方案数为 \(\binom{k}{m}\binom{m}{2m-k}\)
一共染 \(k\) 个，第一次先挑 \(m\) 个染，第二次先把没染的染了再从剩下的挑
前面的相当于 \(t\) 个球染 \(j\) 次，所有的都被染了，二项式反演一下就行
方案数为 \(\sum\limits_{i=0}^t\binom{t}{i}(-1)^{i}(t-i)^j\)
然后就变成了 \(\sum\limits_{j=0}^{m}f_j\sum\limits_{t=0}^m\sum\limits_{k=m}^{2m}\binom{n}{t+k}\binom{k}{m}\binom{m}{2m-k}\sum\limits_{i=0}^t\binom{t}{i}(-1)^{i}(t-i)^j\)
\(\binom{n}{t+k}\) 注意到 \(H(i)\) 为给 \(i\) 个球染色其中第一个球必须染的方案数，你不需要知道到底时哪 \(i\) 个
然后你总共会染 \(t+k\) 个，所以直接 \(\binom{n}{t+k}\)
发现 \(j\) 只在最后有用于是直接挪过去
\(\sum\limits_{t=0}^m\sum\limits_{k=m}^{2m}\binom{n}{t+k}\binom{k}{m}\binom{m}{2m-k}\sum\limits_{i=0}^t\binom{t}{i}(-1)^{i}\sum\limits_{j=0}^m(t-i)^j\)
\(\sum\limits_{j=0}^m(t-i)^j\) 这个东西就相当与给定的多项式第 \(t-i\) 项
然后剩下的就能卷积了，先卷 \(f(t)=\sum\limits_{i=0}^t\binom{t}{i}(-1)^{i}F(t-i)\) 再卷 \(\sum\limits_{t=0}^m\sum\limits_{k=m}^{2m}\binom{n}{t+k}\binom{k}{m}\binom{m}{2m-k}f(t)\)
Code
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,ans,m3,m2;
int f[4194310],g[4194310];
int fac[3000010],inv[3000010],C[3000010];
inline int Binom(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int qpow(int x,int k){
int res=1,base=x;
while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
return res;
}
inline void md(int &x){x=(x>=mod)?x-mod:x;}
inline void mmd(int &x){x=(x>=mod)?x%mod:x;}
namespace POLY{
int len,L,INV;
int r[4194310],G[4194310];
inline void pre(int lim){
for(len=1,L=0;len<=lim;len<<=1,L++);
for(rint i=0;i<len;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
G[0]=1,G[1]=qpow(3,(mod-1)/len);for(rint i=2;i<=len;++i) mmd(G[i]=G[i-1]*G[1]);
}
inline void rev(){G[0]=1,G[1]=qpow(G[1],mod-2);for(rint i=2;i<=len;++i) mmd(G[i]=G[i-1]*G[1]);}
inline void ntt(int a[]){
for(rint i=0;i<len;++i) if(i<r[i]) a[i]^=a[r[i]]^=a[i]^=a[r[i]];
for(rint d=1,t=len>>1;d<len;d<<=1,t>>=1) for(rint i=0;i<len;i+=(d<<1)) for(rint j=0;j<d;j++){
int tmp;mmd(tmp=G[t*j]*a[i+j+d]);
md(a[i+j+d]=a[i+j]-tmp+mod);
md(a[i+j]=a[i+j]+tmp);
}
}
inline void mul(){
ntt(f);ntt(g);for(rint i=0;i<len;++i) mmd(f[i]=f[i]*g[i]);
rev();ntt(f);INV=qpow(len,mod-2);
for(rint i=0;i<len;++i) mmd(f[i]=f[i]*INV);
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
n=read(),m=read();m3=m*3;m2=m+m;
for(rint i=0;i<=m;++i) f[i]=read();
fac[0]=1;for(rint i=1;i<=m3;++i) mmd(fac[i]=fac[i-1]*i);inv[m3]=qpow(fac[m3],mod-2);
inv[0]=1;for(rint i=m3-1;i;i--) mmd(inv[i]=inv[i+1]*(i+1));
C[0]=1;for(rint i=1;i<=m3;++i) mmd(C[i]=C[i-1]*(n-i+1)%mod*inv[i]%mod*fac[i-1]);
for(rint i=0;i<=m;++i) mmd(f[i]=f[i]*inv[i]);
for(rint i=0,r=1;i<=m;i++,r=-r) md(g[i]=(r*inv[i]%mod+mod));
POLY::pre(m2);POLY::mul();
for(rint i=0;i<=m;++i) mmd(f[i]=f[i]*fac[i]);for(rint i=m+1;i<=m2;++i) f[i]=0;
memset(g,0,sizeof(g));
for(rint i=m;i<=m2;++i) mmd(g[i]=Binom(i,m)*Binom(m,m2-i));
POLY::pre(m3);POLY::mul();
for(rint i=m;i<=m3;++i) md(ans=(ans+f[i]*C[i]%mod));
printf("%lld\n",ans);
return 0;
}