【题目记录】计蒜客 - A1616 题解

逃离我推掉我的手 2022-10-15 04:55 146阅读 0赞

[计蒜客 - A1616][- A1616]  
参考[Emcikem][]  
考察内容：模拟 思维  
题目大意：给题目说得很复杂，其实就是给五个长度为100的由‘0’和‘1’组成的字符串，str\[i\]\[j\]等于1就是说第i个人可以pick第j个英雄，要求五个人pick的英雄都不一样，除了询问pick的英雄外，每个人还需要ban五个不同的英雄（和pick的五个英雄也不一样，不受限制的ban），然后还有五个人同样可以不受限制的pick和ban英雄，问有多少种选择方法。

思路：容易想到，除了五个受限制的pick位外，剩下的15个选择位都是不受限的，所以相当于乘上一个常数，即  
 C 95 5 ∗ C 90 5 ∗ C 85 5 C\_\{95\}^5 ∗ C\_\{90\}^5 ∗ C\_\{85\}^5 C955∗C905∗C855

可以预处理得，这个常数为531192758，然后问题就变成了，如何取这五个pick位

相当于就是5\*100的矩阵,要求每一行选择一个下标且权值是1,且都不在同一列.  
表示我方pick的情况,最后在剩下的那一部分,C(95,5)表示我方的部分  
C(90,5)表示敌方ban的部分,C(85,5)表示敌方pick的部分,然后敌方是必须进行全排列的.

想法就是先去选择好我方pick部分,然后ban的部分只能在没有选择的部分里面,这样就不会冲突了,因为一般来说我ban必须在pick之前进行的.

那么设dp\[i\]\[j\]表示当选择第i−1个英雄时, 选择情况为j的情况进行状压,只有5个人,那么就是1<<5  
intdp\[105\]\[1<<5\];

状态转移方程就是  
dp\[i\]\[j\]的转移就是我第i个英雄不选,直接继承dp\[i - 1\]\[j\]的情况.  
第i个英雄选择,继承dp\[i - 1\]\[j ^ (1 << k)\]表示继承于之前的不含有为当前状态的情况.  
答案就是dp\[100\]\[1<<5−1\]  
1<<5−1就是5个都选择的情况.  
时间复杂度 O ( n 2 k ) O(n2^k) O(n2k)

其实也可以直接暴力,就是遍历4个for循环遍历每个人都pick了哪个英雄,然后第5个人就看看还剩下哪些英雄可以选择就可以了,时间复杂度O(1e8)了,数据太水,可以过.

DP解法

#include <iostream>
    #include <string>
    #include <cstring>
    #define ll long long
    #define ld long double
    using namespace std;
    
    const int N = 2e5 + 5, M = 1e6 + 5, MOD = 1e9 + 7, CM = 998244353, INF = 0x3f3f3f3f; 
    const ll linf = 0x7f7f7f7f7f7f7f7f;
    int dp[105][1 << 5]; // 选择第i - 1个英雄时, 选择情况为j
    ll C[105][105], fac[105];
    string s[6];
    
    ll pow(ll a, ll b, ll p) {
        ll ans = 1;
        while (b) {
            if (b & 1) ans = ans * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return ans;
    }
    ll inv(ll a, ll p) {
        return pow(a, p - 2, p);
    }
    ll A(ll n, ll m) {
        if (n < m) return 0;
        return fac[n] * inv(fac[n - m], MOD) % MOD;
    }
    void solve(int kase) {
        fac[0] = 1;
        for (int i = 1; i <= 100; i++) fac[i] = fac[i - 1] * i % MOD;
        C[0][0] = 1;
        for (int i = 1; i <= 100; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
            }
        }
        while (cin >> s[0]) {
            for (int i = 1; i < 5; i++) cin >> s[i];
            memset(dp, 0, sizeof(dp));
            dp[0][0] = 1;
            for (int i = 1; i <= 100; i++) {
                for (int j = 0; j < (1 << 5); j++) dp[i][j] = dp[i - 1][j];// 当前所有物品都不选的情况
                for (int j = 0; j < (1 << 5); j++) {
                    for (int k = 0; k < 5; k++) {
                        if ((j & (1 << k)) && (s[k][i - 1] == '1')) { // 当第i - 1个英雄被k pick时
                            dp[i][j] = (dp[i][j] + dp[i - 1][j ^ (1 << k)]) % MOD; // 选择这个物品,继承于之前的不含有为当前状态的情况
                        }
                    }
                }
            }
            ll ans = dp[100][(1 << 5) - 1];
            printf("%lld\n", A(95, 5) * C[90][5] % MOD * C[85][5] % MOD * ans % MOD);
        }
    }
    int main() {
        solve(1);
    
        return 0;
    }

暴力解法

#include<iostream>
    #include<string>
    #include<bitset>
    using namespace std;
    typedef long long ll;
    
    const int inf=0x3f3f3f3f;
    const int mod=1e9+7;
    
    string str[5];
    bitset<105>fl;
    bitset<105>vis;
    ll ans=0;
    void dfs(int num,int sum)
    {
    	if(num==4)
    	{
    		ans+=sum;
    		ans%=mod;
    		return;
    	}
    	for(int i=0;i<str[num].size();i++)
    	{
    		if(str[num][i]=='1'&&(!vis[i]))
    		{
    			vis.set(i);
    			if(str[4][i]=='1')dfs(num+1,sum-1);
    			else dfs(num+1,sum);
    			vis.reset(i);
    		}
    	}
    }
    int main()
    {
    	while(cin>>str[0])
    	{
    		rep(i,1,5)
    		{
    			cin>>str[i];
    		}
    		int lins=0;
    		rep(i,0,str[4].size())
    		{
    			if(str[4][i]=='0')fl.reset(i);
    			else fl.set(i),lins++;
    		}
    		ans=0;
    		vis.reset();
    		dfs(0,lins);
    		ans*=531192758ll;
    		ans%=mod;
    		cout<<ans<<endl;
    	}
    }

[- A1616]: https://nanti.jisuanke.com/t/A1616
[Emcikem]: https://www.cnblogs.com/Emcikem/