P7481 梦现时刻题解（洛谷4月月赛 D）

冷月葬T魂 · 2021-04-11 20:25:12 · 题解

题目大意：给定正整数 n,m，令 F(a,b)=\sum\limits_{i=1}^m C_b^i \times C_{n-i}^a ，求 \bigoplus_{a=1}^m \bigoplus_{b=1}^m F(a,b)（其中 \bigoplus 表示异或运算）。

看似是一道数学题，但是我们可以将它“实际化”来做。

我们可以将 C_b^i \times C_{n-i}^a 视为从 n 个球中按两步取球：第一步从前 b 个球中取出 i 个球，第二步从剩下的 n-i 个球中取出 a 个球。
于是，F(a,b)=\sum\limits_{i=1}^m C_b^i \times C_{n-i}^a 即代表着第一步从前 b 个球中取出若干个球，第二步从剩下的球中取出 a 个球的取法总数。

我们现设 f(i,j) 表示第一步从前 i 个球中取出若干个球，第二步从剩下的球中取出 j 个球的取法总数，则题意即对于 1 \leq i \leq m,1 \leq j \leq m 求出 f(i,j) 的值。注意此处的 i 和题目中的 i 意义并不相同。

这样我们就把一道数学问题转化成了一道动态规划问题。

为了方便，我们再设 g(i,j) 表示第一步从前 i 个球中取出若干个球，第二步从剩下的球中取出 j 个球但不能取第 i+1 个球的取法总数。

得出递推式：

f(i,j)=f(i-1,j)+g(i-1,j)
其中 f(i-1,j) 表示第一步不取第 i 个球（第二步仍然可以取），g(i-1,j) 表示第一步取第 i 个球（第二步就不能取了）。
g(i,j)=f(i,j)-g(i,j-1)
其中 f(i,j) 代表第二步取不取第 i+1 个球无所谓，g(i,j-1) 代表第二步取第 i+1 个球（于是只能从剩下的球中取出 j-1 个，且不能取第 i+1 个球）。

边界条件： f(0,j)=C_n^j,f(i,0)=2^i,g(0,j)=C_{n-1}^{j},g(i,0)=2^i 。

原来的 g(0,j) 边界条件写错了，现已修改。感谢 @panyf 提出错误。

至于 C_n^j 可以通过预处理 j 的乘法逆元递推求出。

算法时间复杂度为 O(m^2)。~~（究竟赛时没有做出来）~~

附上代码：

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,val) memset(a,val,sizeof(a))
#define int long long
using namespace std;

// f(i,j)=g(i-1,j)+f(i-1,j)
// g(i,j)=f(i,j)-g(i,j-1)
// f(0,i)=C(n,i)
// f(i,0)=2^n
// g(0,i)=C(n-1,i)
// g(i,0)=2^n

const int N=5e3+5,mod=998244353;

int n,m,f[N][N],g[N][N];
int inv[N];

int qpow(int x,int y)
{
    int res=1;
    while(y){
        if(y&1ll) res=res*x%mod;
        x=x*x%mod;
        y>>=1ll;
    }
    return res;
}

signed main()
{
    cin>>n>>m;

    inv[0]=1;
    For(i,1,m){
        inv[i]=qpow(i,mod-2);
    }

    f[0][0]=1;

    For(i,1,m){
        f[0][i]=f[0][i-1]*(n-i+1)%mod*inv[i]%mod;
        f[i][0]=f[i-1][0]*2%mod;
    }

    g[0][0]=1;

    For(i,1,m){
        g[0][i]=g[0][i-1]*(n-i)%mod*inv[i]%mod;
        g[i][0]=g[i-1][0]*2%mod;
    }

    int ans=0;

    For(i,1,m){
        For(j,1,m){
            f[i][j]=(g[i-1][j]+f[i-1][j])%mod;
            g[i][j]=((f[i][j]-g[i][j-1])%mod+mod)%mod;
            ans^=f[i][j];
        }
    }

    cout<<ans<<endl;

    return 0;
}

另：这是本人的第一篇题解，若有不到之处望大家多多包涵：）

P7481 梦现时刻 题解 （洛谷4月月赛 D）

P7481 梦现时刻题解（洛谷4月月赛 D）