[NOI2019] 斗主地

文章目录

• • • 题面
    • 得分情况
    • 题解
    • • 10pts: n ≤ 10 nleq 10 n≤10
      • 30pts: n ≤ 80 nleq 80 n≤80
      • 40pts: 所有 A i A_i Ai​相同
      • 100pts idea1:
      • 100pts idea2:

题面

题面

得分情况

100pts: 16
>40pts: 26
40pts: 159
30pts: 149

题解 10pts: n ≤ 10 nleq 10 n≤10

暴搜

30pts: n ≤ 80 nleq 80 n≤80

dp
设 f i , j f_{i,j} fi,j​为左边 i i i张牌，右边 j j j张牌的概率。
讨论移左边还是移右边就行了。

参考代码:

for(int i=1;i<=m;i++){
    memset(f,0,sizeof(f));memset(h,0,sizeof(h));
    f[a[i]][n-a[i]]=1;
    for(int j=1;j<=a[i];j++) l[j]=g[j];
    for(int j=1;j<=n-a[i];j++) r[j]=g[j+a[i]];
    for(int j=a[i];~j;j--)
        for(int k=n-a[i];~k;k--){
            if(!f[j][k]) continue;
            if(j>0){
                ll tmp=f[j][k]*j%mod*inv(j+k)%mod;
                f[j-1][k]+=tmp;f[j-1][k]%=mod;
                h[n-j-k+1]+=tmp*l[j]%mod;h[n-j-k+1]%=mod;
            }
            if(k>0){
                ll tmp=f[j][k]*k%mod*inv(j+k)%mod;
                f[j][k-1]+=tmp;f[j][k-1]%=mod;
                h[n-j-k+1]+=tmp*r[k]%mod;h[n-j-k+1]%=mod;
            }
        }
    for(int j=1;j<=n;j++) g[j]=h[n-j+1];
}

40pts: 所有 A i A_i Ai​相同

前30pts采用dp暴力做。
对于 A i A_i Ai​全相同的10pts,算出系数，做矩乘即可。

参考代码:

#include
#define ll long long
#define uit unsigned int
using namespace std;
const int N=105,MAXN=5e5+10;
const int M=998244353,mod=M;
int n,m,type,Q,f[N],A[MAXN],sc[N][N],cir[N],pw[N];
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void Add(int&a,const int&b){a=a+b>=mod?a+b-mod:a+b;}
inline void Dec(int&a,const int&b){a=a>=b?a-b:a-b+mod;}
inline void Mul(int&a,const int&b){a=(ll)a*b%mod;}
inline int ftp(int b,int p){
    int r=1;
    while(p){
        if(p&1) r=mul(r,b)%M;
        b=1ll*mul(b,b)%M;
        p>>=1;
    }
    return r;
}
struct MAT{
    int mat[N][N],h,l;
    MAT(){h=l=0;memset(mat,0,sizeof mat);}
    friend MAT operator *(const MAT &a,const MAT &b){
        MAT ret;ret.h=a.h;ret.l=b.l;
        for(int i=1;i<=a.h;i++)
            for(int j=1;j<=b.l;j++)
                for(int k=1;k<=a.l;k++)
                    Add(ret.mat[i][j],mul(a.mat[i][k],b.mat[k][j]));
        return ret;
    }
    friend inline MAT operator^(MAT a,int p){
        MAT ret;ret.h=a.h;ret.l=a.l;
        for(int i=1;i<=ret.h;i++) ret.mat[i][i]=1;
        while(p){
            if(p&1) ret=ret*a;
            a=a*a;
            p>>=1;
        }
        return ret;
    }
};
bool check(){
    for(int i=1;i<=m;i++) if(A[i]!=A[1]) return 0;
    return 1;
}
void all_A_is_same(){
    int n1=A[1],n2=n-A[1];
    MAT S,B;
    B.h=1,B.l=n;for(int i=1;i<=n;i++) B.mat[1][i]=f[i];
    S.h=S.l=n;
    for(int i=n1;~i;i--) for(int j=n2;~j;j--) if(i+j>0){
        if(i+j==n1+n2) sc[i][j]=1;
        else sc[i][j]=mul(cir[i+j+1],add(mul(i^n1?i+1:0,sc[i+1][j]),mul(j^n2?j+1:0,sc[i][j+1])));
        if(i) Add(S.mat[i][i+j],mul(sc[i][j],mul(cir[i+j],i)));
        if(j) Add(S.mat[n1+j][i+j],mul(sc[i][j],mul(cir[i+j],j)));
    }
//    for(int i=1;i<=n1;i++){
//        for(int j=1;j<=n2;j++) cout<
        scanf("%d",&x);
        printf("%dn",B.mat[1][x]);
    }
}
int main(){
//    freopen(".in","r",stdin);
//    freopen("123.out","w",stdout);
    scanf("%d%d%d",&n,&m,&type);
    for(int i=1;i<=n;i++) f[i]=mul(i,type==1?1:i);
    for(int i=1;i<=m;i++) scanf("%d",&A[i]);
    cir[1]=1;for(int i=2;i<=n;i++) cir[i]=1ll*cir[M%i]*(M-M/i)%M;
    if(check()){all_A_is_same();}
    return 0;
}

100pts idea1:

f ( i ) = i   o r   i 2 f(i)=ispace orspace i^2 f(i)=i or i2。
可以猜出结论:一次函数洗牌后的期望还是一次函数，二次函数洗牌后的期望还是二次函数。
即:设洗牌前 a i a_i ai​为 k k k次多项式，则洗牌后 a i ′ a_i^{'} ai′​仍为 k k k次多项式。
这里先假设该结论成立，之后再证明。
那么设某一次洗牌后第 i i i张(从上往下数)的期望为 x i ′ x_i^{'} xi′​,洗牌前第 i i i张的期望为 x i x_i xi​。
可得:
x 1 ′ = A n x 1 + n − A n x A + 1 x n ′ = A n x A + n − A n x n x 2 ′ = A n ( A − 1 n − 1 x 2 + n − A n − 1 x A + 1 ) + n − A n ( A n − 1 x 1 + n − A − 1 n − 1 x A + 2 ) x_1^{'}=frac{A}{n}x_1+frac{n-A}{n}x_{A+1}\ x_n^{'}=frac{A}{n}x_A+frac{n-A}{n}x_n\ x_2^{'}=frac{A}{n}(frac{A-1}{n-1}x_2+frac{n-A}{n-1}x_{A+1})+frac{n-A}{n}(frac{A}{n-1}x_1+frac{n-A-1}{n-1}x_{A+2}) x1′​=nA​x1​+nn−A​xA+1​xn′​=nA​xA​+nn−A​xn​x2′​=nA​(n−1A−1​x2​+n−1n−A​xA+1​)+nn−A​(n−1A​x1​+n−1n−A−1​xA+2​)

这里举 x 1 ′ x_1^{'} x1′​为例证明上述式子。
由与洗牌前后同一堆内的牌先后顺序不变，所以 x 1 ′ x_1^{'} x1′​显然由 x 1 x_1 x1​和 x A + 1 x_{A+1} xA+1​得来。
考虑系数怎么计算。
以 A n x 1 frac{A}{n}x_1 nA​x1​为例:
想象一个取数的操作序列，若要使 x 1 x_1 x1​为最后取的第一张牌，那么 x 1 x_1 x1​必然在该长度为 n n n的序列的最后一个位置，那么在此之前有 n − 1 n-1 n−1张，与 x 1 x_1 x1​来自同一堆的牌有 A − 1 A-1 A−1张。
那么 x 1 x_1 x1​为最后一张的操作序列有 C n − 1 A − 1 C_{n-1}^{A-1} Cn−1A−1​种，无限制的操作序列总共有 C n A C_n^A CnA​种，故 x 1 x_1 x1​的系数为 C n − 1 A − 1 C n A = A n frac{C_{n-1}^{A-1}}{C_n^A}=frac{A}{n} CnA​Cn−1A−1​​=nA​.
其他同理。

那么我们就得到了 x i x_i xi​的递推式。
同时, x i x_i xi​可以表示成 a i 2 + b i + c ai^2+bi+c ai2+bi+c的形式。
最开始，根据题目数据， x i = i   o r   i 2 x_i=ispace orspace i^2 xi​=i or i2,即 a = c = 0 , b = 1 a=c=0,b=1 a=c=0,b=1或 a = 1 , b = c = 0 a=1,b=c=0 a=1,b=c=0。
根据递推式可以得到 x i ′ x_i^{'} xi′​，根据结论， x i ′ x_i^{'} xi′​仍可以表示成 a ′ i 2 + b ′ i + c ′ a^{'}i^2+b^{'}i+c^{'} a′i2+b′i+c′的形式，通过拉格朗日插值或待定系数解放方程可以得到新的 a ′ a^{'} a′, b ′ b^{'} b′, c ′ c^{'} c′。
以此类推，我们就得到了某次洗牌后期望的多项式表达式。
每次询问 O ( 1 ) O(1) O(1)计算输出即可。

参考代码如下:(这里采用了拉格朗日插值求系数)

#include
#define ll long long
#define uit unsigned int
using namespace std;
const ll M=998244353ll;
const int N=1e7+5;
int m,tp,Q;ll n,a,b,c,f[N];
ll ftp(ll b,ll p){
    b=(b%M+M)%M;
    ll r=1;
    while(p){
        if(p&1) r=r*b%M;
        b=b*b%M;
        p>>=1;
    }
    return r%M;
}
ll calc(ll x){
    return ((a*x%M+b)%M*x%M+c)%M;
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    scanf("%lld%d%d",&n,&m,&tp);
    if(tp==1) a=c=0,b=1;
    else a=1,b=c=0;
    ll npw=1ll*n*n%M;
    ll _=ftp(n,M-2),__=ftp(n-1,M-2),___=ftp(npw-3ll*n+2ll,M-2);
    while(m--){
        ll t,t1,t2,t3;
        scanf("%lld",&t);
        t1=(t*calc(1)%M+(n-t+M)%M*calc(t+1)%M)*_%M;
        t2=(((t-1ll+M)%M*calc(2)%M+(n-t+M)%M*calc(t+1)%M)%M*t%M+(t*calc(1)%M+(n-t-1ll+M)%M*calc(t+2)%M)%M*((n-t+M)%M)%M)%M*_%M*__%M;
        t3=(t*calc(t)%M+(n-t+M)%M*calc(n)%M)%M*_%M;
        a=(((n-2+M)%M*t1%M+(1-n+M)%M*t2%M)%M+t3)%M*___%M;
        b=(((n+2ll)*((2ll-n+M)%M)%M*t1%M+(n+1ll)*((n-1ll+M)%M)%M*t2%M)%M+(M-3ll)*t3%M)%M*___%M;
        c=(((2ll*n%M*((n-2ll+M)%M)%M)*t1%M+(1ll-n+M)%M*n%M*t2%M)%M+2ll*t3%M)%M*___%M;
    }
    for(int i=1;i<=n;i++) f[i]=(calc(i)+M)%M;
    scanf("%d",&Q);
    while(Q--){
        int x;scanf("%d",&x);
        printf("%lldn",f[x]);
    }
    return 0;
}

对于结论:一次函数洗牌后的期望还是一次函数，二次函数洗牌后的期望还是二次函数,有一种感性且扯蛋的证明方式。

设洗牌前第 i i i张的期望是 a i a_i ai​,洗牌后为 a i ′ a_i^{'} ai′​,考虑洗牌后的第 i i i张是洗牌前的第 j j j张的概率。
这里假设 j < = A j<=A j<=A,容易得到其对 a i ′ a_i^{'} ai′​的贡献为:
1 ( n A ) ∑ j = 1 A a j ( i − 1 j − 1 ) ( n − i A − j ) frac{1}{tbinom{n}{A}}sum_{j=1}^Aa_jtbinom{i-1}{j-1}tbinom{n-i}{A-j} (An​)1​j=1∑A​aj​(j−1i−1​)(A−jn−i​)
这个式子本质上和之前推导 x i x_i xi​的式子相同。
由于 k k k次下降幂多项式和 k k k次多项式一一对应，这里将 a j a_j aj​代入为 ( j − 1 ) k ‾ (j-1)^{underline{k}} (j−1)k​。
得:
1 ( n A ) ∑ j = 1 A a j ( i − 1 j − 1 ) ( n − i A − j ) = 1 ( n A ) ∑ j = 1 A ( j − 1 ) k ‾ ( i − 1 j − 1 ) ( n − i A − j ) = 1 ( n A ) ∑ j = 1 A k ! ( j − 1 k ) ( i − 1 j − 1 ) ( n − i A − j ) = k ! ( n A ) ∑ j = 1 A ( j − 1 k ) ( i − 1 j − 1 ) ( n − i A − j ) frac{1}{tbinom{n}{A}}sum_{j=1}^Aa_jtbinom{i-1}{j-1}tbinom{n-i}{A-j} \ =frac{1}{tbinom{n}{A}}sum_{j=1}^A(j-1)^{underline{k}}tbinom{i-1}{j-1}tbinom{n-i}{A-j}\ =frac{1}{tbinom{n}{A}}sum_{j=1}^Ak!tbinom{j-1}{k}tbinom{i-1}{j-1}tbinom{n-i}{A-j}\ =frac{k!}{tbinom{n}{A}}sum_{j=1}^{A}tbinom{j-1}{k}tbinom{i-1}{j-1}tbinom{n-i}{A-j} (An​)1​j=1∑A​aj​(j−1i−1​)(A−jn−i​)=(An​)1​j=1∑A​(j−1)k​(j−1i−1​)(A−jn−i​)=(An​)1​j=1∑A​k!(kj−1​)(j−1i−1​)(A−jn−i​)=(An​)k!​j=1∑A​(kj−1​)(j−1i−1​)(A−jn−i​)
由 ( a b ) ( c a ) = ( c b ) ( c − b a − b ) tbinom{a}{b}tbinom{c}{a}=tbinom{c}{b}tbinom{c-b}{a-b} (ba​)(ac​)=(bc​)(a−bc−b​),令 j − 1 = a , k = b , i − 1 = c j-1=a,k=b,i-1=c j−1=a,k=b,i−1=c得:
k ! ( n A ) ∑ j = 1 A ( j − 1 k ) ( i − 1 j − 1 ) ( n − i A − j ) = k ! ( n A ) ∑ j = 1 A ( i − 1 k ) ( i − 1 − k j − 1 − k ) ( n − i A − j ) = k ! ( n A ) ( i − 1 k ) ∑ j ( i − 1 − k j − 1 − k ) ( n − i A − j ) = k ! ( n A ) ( i − 1 k ) ∑ j ( i − 1 − k j ) ( n − i A − j − 1 − k ) frac{k!}{tbinom{n}{A}}sum_{j=1}^{A}tbinom{j-1}{k}tbinom{i-1}{j-1}tbinom{n-i}{A-j}\ =frac{k!}{tbinom{n}{A}}sum_{j=1}^{A}tbinom{i-1}{k}tbinom{i-1-k}{j-1-k}tbinom{n-i}{A-j}\ =frac{k!}{tbinom{n}{A}}tbinom{i-1}{k}sum_{j}tbinom{i-1-k}{j-1-k}tbinom{n-i}{A-j}\ =frac{k!}{tbinom{n}{A}}tbinom{i-1}{k}sum_{j}tbinom{i-1-k}{j}tbinom{n-i}{A-j-1-k} (An​)k!​j=1∑A​(kj−1​)(j−1i−1​)(A−jn−i​)=(An​)k!​j=1∑A​(ki−1​)(j−1−ki−1−k​)(A−jn−i​)=(An​)k!​(ki−1​)j∑​(j−1−ki−1−k​)(A−jn−i​)=(An​)k!​(ki−1​)j∑​(ji−1−k​)(A−j−1−kn−i​)
(上式最后一行把 j j j用 j + 1 + k j+1+k j+1+k代替)
由 ∑ j ( n j ) ( m k − j ) = ( n + m k ) sum_{j}tbinom{n}{j}tbinom{m}{k-j}=tbinom{n+m}{k} ∑j​(jn​)(k−jm​)=(kn+m​)，令 i − 1 − k = n , n − i = m , A − 1 − k = k i-1-k=n,n-i=m,A-1-k=k i−1−k=n,n−i=m,A−1−k=k,得:
k ! ( n A ) ( i − 1 k ) ∑ j ( i − 1 − k j ) ( n − i A − j − 1 − k ) = k ! ( n A ) ( i − 1 k ) ( i − 1 − k + n − i A − 1 − k ) = k ! ( n A ) ( i − 1 k ) ( n − k − 1 A − k − 1 ) = k ! ( i − 1 ) ! k ! ( i − 1 − k ) ! ( n − k − 1 A − k − 1 ) ( n A ) = ( i − 1 ) ! ( i − 1 − k ) ! ( n − k − 1 A − k − 1 ) ( n A ) = ( i − 1 ) k ‾ ( n − k − 1 A − k − 1 ) ( n A ) frac{k!}{tbinom{n}{A}}tbinom{i-1}{k}sum_{j}tbinom{i-1-k}{j}tbinom{n-i}{A-j-1-k}\ =frac{k!}{tbinom{n}{A}}tbinom{i-1}{k}tbinom{i-1-k+n-i}{A-1-k}\ =frac{k!}{tbinom{n}{A}}tbinom{i-1}{k}tbinom{n-k-1}{A-k-1}\ =k!frac{(i-1)!}{k!(i-1-k)!}frac{tbinom{n-k-1}{A-k-1}}{tbinom{n}{A}}\ =frac{(i-1)!}{(i-1-k)!}frac{tbinom{n-k-1}{A-k-1}}{tbinom{n}{A}}\ =(i-1)^{underline{k}}frac{tbinom{n-k-1}{A-k-1}}{tbinom{n}{A}} (An​)k!​(ki−1​)j∑​(ji−1−k​)(A−j−1−kn−i​)=(An​)k!​(ki−1​)(A−1−ki−1−k+n−i​)=(An​)k!​(ki−1​)(A−k−1n−k−1​)=k!k!(i−1−k)!(i−1)!​(An​)(A−k−1n−k−1​)​=(i−1−k)!(i−1)!​(An​)(A−k−1n−k−1​)​=(i−1)k​(An​)(A−k−1n−k−1​)​
发现当 a j a_j aj​为 k k k次下降幂时，这一部分也是 k k k次下降幂，对于 j > A j>A j>A的部分同理，所以 a i ′ a_i^{'} ai′​也是 k k k次下降幂。
进一步的说，若 a i a_i ai​为 k k k次多项式时， a i ′ a_i^{'} ai′​是不多于 k k k次的多项式。
于是我们就证明了之前的结论。
考场上还是打表猜结论吧。

100pts idea2:

正着做有点难，考虑倒着做。
发现其逆过程就是等概率拎两个序列出来，把一个序列放在最前面。
这样的操作进行 m m m轮，就是Base为 2 2 2的基数排序。
那么 E [ i ] E[i] E[i]就是某个数基排之后在这个数前面的概率之和; E [ i 2 ] E[i^2] E[i2]就是选两个数基排之后在前你前面的概率之和。
DP即可。