CodeForces - 1017D Round #502 D. The Wu（状压预处理）

D. The Wu time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Childan is making up a legendary story and trying to sell his forgery — a necklace with a strong sense of "Wu" to the Kasouras. But Mr. Kasoura is challenging the truth of Childan's story. So he is going to ask a few questions about Childan's so-called "personal treasure" necklace.

This "personal treasure" is a multiset $\mathrm{SS of mm "01-strings".}$

A "01-string" is a string that contains $\mathrm{nn characters\; "0"\; and\; "1".\; For\; example,\; if n=4n=4,\; strings\; "0110",\; "0000",\; and\; "1110"\; are\; "01-strings",\; but\; "00110"\; (there\; are 55 characters,\; not 44)\; and\; "zero"\; (unallowed\; characters)\; are\; not.}$

Note that the multiset $\mathrm{SS can\; contain\; equal\; elements.}$

Frequently, Mr. Kasoura will provide a "01-string" $\mathrm{tt and\; ask\; Childan\; how\; many\; strings ss are\; in\; the\; multiset SS such\; that\; the\; "Wu"\; value\; of\; the\; pair (s,t)(s,t) is not\; greater than kk.}$

Mrs. Kasoura and Mr. Kasoura think that if ${\mathrm{si=tisi=ti (1\le i\le n1\le i\le n)\; then\; the\; "Wu"\; value\; of\; the\; character\; pair\; equals\; to wiwi,\; otherwise 00.\; The\; "Wu"\; value\; of\; the\; "01-string"\; pair\; is\; the\; sum\; of\; the\; "Wu"\; values\; of\; every\; character\; pair.\; Note\; that\; the\; length\; of\; every\; "01-string"\; is\; equal\; to nn.}}^{}$

For example, if $\mathrm{w=[4,5,3,6]w=[4,5,3,6],\; "Wu"\; of\; ("1001",\; "1100")\; is 77 because\; these\; strings\; have\; equal\; characters\; only\; on\; the\; first\; and\; third\; positions,\; so w1+w3=4+3=7w1+w3=4+3=7.}$

You need to help Childan to answer Mr. Kasoura's queries. That is to find the number of strings in the multiset $\mathrm{SS such\; that\; the\; "Wu"\; value\; of\; the\; pair\; is\; not\; greater\; than kk.}$

Input

The first line contains three integers $\mathrm{nn, mm,\; and qq (1\le n\le 121\le n\le 12, 1\le q,m\le 5\cdot 1051\le q,m\le 5\cdot 105) —\; the\; length\; of\; the\; "01-strings",\; the\; size\; of\; the\; multiset SS,\; and\; the\; number\; of\; queries.}$

The second line contains $\mathrm{nn integers w1,w2,\dots ,wnw1,w2,\dots ,wn (0\le wi\le 1000\le wi\le 100) —\; the\; value\; of\; the ii-th\; caracter.}$

Each of the next $\mathrm{mm lines\; contains\; the\; "01-string" ss of\; length nn —\; the\; string\; in\; the\; multiset SS.}$

Each of the next $\mathrm{qq lines\; contains\; the\; "01-string" tt of\; length nn and\; integer kk (0\le k\le 1000\le k\le 100) —\; the\; query.}$

Output

For each query, print the answer for this query.

Examples input Copy 2 4 540 200101101100 2000 4011 2011 4011 60 output Copy 24234 input Copy 1 2 4100010 00 1001 01 100 output Copy 1212 Note

In the first example, we can get:

"Wu" of ("01", "00") is $4040.$

"Wu" of ("10", "00") is $2020.$

"Wu" of ("11", "00") is $00.$

"Wu" of ("01", "11") is $2020.$

"Wu" of ("10", "11") is $4040.$

"Wu" of ("11", "11") is $6060.$

In the first query, pairs ("11", "00") and ("10", "00") satisfy the condition since their "Wu" is not greater than $2020.$

In the second query, all strings satisfy the condition.

In the third query, pairs ("01", "11") and ("01", "11") satisfy the condition. Note that since there are two "01" strings in the multiset, the answer is $\mathrm{22,\; not 11.}$

In the fourth query, since $\mathrm{kk was\; increased,\; pair\; ("10",\; "11")\; satisfies\; the\; condition\; too.}$

In the fifth query, since $\mathrm{kk was\; increased,\; pair\; ("11",\; "11")\; satisfies\; the\; condition\; too.}$

 

 

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #define MAX 500005 #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int a[MAX]; char s[MAX][20]; char ss[20]; ll dp[(1<<12)+5][105]; int b[(1<<12)+5]; int main() { int n,m,q,x,i,j,k; scanf("%d%d%d",&n,&m,&q); for(i=0;i<n;i++){ scanf("%d",&a[i]); } for(i=0;i<m;i++){ scanf(" %s",s[i]); } for(i=0;i<m;i++){ ll S=0; for(j=0;j<n;j++){ if(s[i][j]=='1') S|=1<<j; } b[S]++; } for(i=0;i<(1<<n);i++){ for(j=0;j<(1<<n);j++){ if(!b[j]) continue; int sum=0; for(k=0;k<n;k++){ if((i&(1<<k))==(j&(1<<k))) sum+=a[k]; } if(sum>100) continue; dp[i][sum]+=b[j]; } } while(q--){ scanf(" %s %d",ss,&x); ll S=0; for(i=0;i<n;i++){ if(ss[i]=='1') S|=1<<i; } ll ans=0; for(i=0;i<=x;i++){ ans+=dp[S][i]; } printf("%I64d\n",ans); } return 0; }

 

转载于:https://www.cnblogs.com/yzm10/p/9451427.html

相关资源：数据结构—成绩单生成器