题目链接

5 friends play LOL together . Every one should BAN one character and PICK one character . The enemy should BAN 55 characters and PICK 55 characters . All these 2020 heroes must be different .

Every one can BAN any heroes by his personal washes . But he can only PICK heroes which he has bought .

Suppose the enemy can PICK or BAN any heroes. How many different ways are there satisfying the conditions?

For example , a valid way is :

Player 11 : picks hero 11, bans hero 22

Player 22 : picks hero 33, bans hero 44

Player 33 : picks hero 5, bans hero 66

Player 44 : picks hero 77, bans hero 88

Player 55 : picks hero 99, bans hero 1010

Enemies pick heroes 11,12,13,14,1511,12,13,14,15 , ban heroes 16,17,18,19,2016,17,18,19,20 .

Input
The input contains multiple test cases.(No more than 2020)

In each test case . there’s 55 strings S[1] \sim S[5]S[1]∼S[5] ,respectively whose lengths are 100100 , For the ii-th person if he has bought the jj-th hero, the jj-th character of S[i]S[i] is ‘11’, or ‘00’ if not. The total number of heroes is exactly 100100 .

Output
For each test case , print the answer mod 10000000071000000007 in a single line .

样例输入
0110011100011001001100011110001110001110001010010111111110101010010011010000110100011001001111101011
1000111101111110110100001101001101010001111001001011110001111110101000011101000001011100001001011010
0100101100011110011100110110011100111100010010011001111110101111111000000110001110000110001100001110
1110010101010001000110100011101010001010000110001111111110101010000000001111001110110101110000010011
1000010011111110001101100000101001110100011000111010011111110110111010011111010110101111011111011011
样例输出
515649254
题目来源
ACM-ICPC 2017 Asia Xi’an


/* 0110011100011001001100011110001110001110001010010111111110101010010011010000110100011001001111101011 1000111101111110110100001101001101010001111001001011110001111110101000011101000001011100001001011010 0100101100011110011100110110011100111100010010011001111110101111111000000110001110000110001100001110 1110010101010001000110100011101010001010000110001111111110101010000000001111001110110101110000010011 1000010011111110001101100000101001110100011000111010011111110110111010011111010110101111011111011011 */
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<string.h>
using namespace std;
char a[10][222];
long long sum,ans;
const long long mod = 1e9+7;
int book[222];
int dis[222];
void dfs(int x)
{
     if(x==5)
     {
         ans=(sum+ans);
         for(int i=1;i<=4;i++)
         {
             if(a[5][dis[i]]=='1')
                ans--;
         }

         ans = ans%mod;
         return ;
     }
     for(int i=0;i<100;i++)
     {
        if(book[i]==0&&a[x][i]=='1')
        {
            book[i] = 1;
            dis[x] = i;
            dfs(x+1);
            book[i] = 0;
        }
     }
}
int main()
{
    while(cin>>a[1])
    {
        for(int i=2;i<=5;i++)
        {
            cin>>a[i];
        }
        ans = 0;
        sum = 0;
        memset(book,0,sizeof book);
        for(int i=0;i<100;i++)
            if(a[5][i]=='1')sum++;
            dfs(1);
        ans = (ans*531192758)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

dp版o( 5！* 500)
参考博客
code:

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<string.h>
using namespace std;
char a[10][222];
long long sum,ans;
const long long mod = 1e9+7;
int book[222];
int dis[222];
long long dp[10][222];
void dfs(int t)
{
    if(t==5)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=100;i++)
        {
            dp[1][i] = dp[1][i-1];
            if(a[1][i]=='1')dp[1][i]++;
        }
        for(int i=2;i<=5;i++)
        {
            for(int j=1;j<=100;j++)
            {
                dp[i][j] = dp[i][j-1];
                if(a[i][j]=='1')dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
            }
        }
        ans = (ans+dp[5][100])%mod;
        return ;
    }
    for(int i=t;i<=5;i++)
    {
        swap(a[i],a[t]);
        dfs(t+1);
        swap(a[i],a[t]);
    }
}
int main()
{
    long long tmp = 531192758;
    while(~scanf("%s",a[1]+1))
    {
        for(int i=2;i<=5;i++)
        {
            scanf("%s",a[i]+1);
        }
        ans = 0;
        sum = 0;
        memset(book,0,sizeof book);
            dfs(1);
        ans = (ans*tmp)%mod;
        cout<<ans<<endl;
    }
    return 0;
}