班服状态压缩DP

题目描述：

要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod 1000000007后的答案。

输入描述：

共有T组数据。

对于每组数据，第一行为一个整数n，表示有n个班级。

2~n+1行，每行有最多100个数字，表示第i-1班待选班服的编号。

输出描述：

对于每组数据，输出方案总数 mod 1000000007后的答案。

样例输入：

3 5

8 100

5 100 1

5 100

样例输出：

数据范围：

对于30%的数据，1<=T<=3, 1<=n<=3，每班待选样式不超过10种。

对于50%的数据，1<=T<=5, 1<=n<=5，每班待选样式不超过50种。

对于100%的数据，1<=T<=10, 1<=n<=10，每班待选样式不超过100种。

分析:

如果注意到n $\leq$ 10 应该发现这是道状态压缩题.

考试的时候一直当成计数题做.然而想多了.

其实就是将班级状态压缩.然后根据校服来进行转移.

#include<cstdio>//BAONI
#include<cstring>
#include<algorithm>
using namespace std;
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

const int Mod=1000000007;
int n;
int F[110][1050];
int A[20][110];

int main()
{
	freopen("shirt.in","r",stdin);
	freopen("shirt.out","w",stdout);
	int t;
	read(t);
	while(t--)
	{
		memset(F,0,sizeof(F));
		memset(A,0,sizeof(A));
		read(n);
		//printf("%d\n",n);
		for(int i=1;i<=n;++i)
		{
			int k=0;char ch=getchar();
			while(true)
			{
				if(ch<'0'||ch>'9'){
					A[i][k]=1;
					k=0;
				}
				if(ch<='9'&&ch>='0'){
					k=(k<<1)+(k<<3)+(ch^48);
				}
				ch=getchar();
				if(ch=='\n')break;
			}
			A[i][k]=1;
		}

		/*
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=100;++j)
				if(A[i][j])printf("%d ",j);
			printf("\n");
		}
		*/

		F[0][0]=1;

		for(int i=1;i<=100;++i)
		{
			for(int j=0;j<(1<<n);++j)
			{
				F[i][j]=F[i-1][j];
			}

			for(int j=1;j<=n;++j)
			{
				if(!A[j][i])continue;
				for(int k=0;k<=(1<<n)-1;++k)
				{
					if(k&(1<<(j-1)))continue;
					F[i][k+(1<<(j-1))]=(F[i][k+(1<<(j-1))] + F[i-1][k])%Mod;
				}
			}
		}

		/*
		for(int i=1;i<=100;++i)
		{
			for(int j=1;j<=(1<<n)-1;++j)
				printf("%d ",F[i][j]);
			printf("\n");
		}
		*/
		int tot=(1<<n)-1;
		printf("%d\n",F[100][tot]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

#include<cstdio>//BAONI

#include<cstring>

#include<algorithm>

using namespace std;

template<class T>void read(T &x)

{

x=0;int f=0;char ch=getchar();

while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }

while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

x = f ? -x : x;

return ;

}

const int Mod=1000000007;

int n;

int F[110][1050];

int A[20][110];

int main()

{

freopen("shirt.in","r",stdin);

freopen("shirt.out","w",stdout);

int t;

read(t);

while(t--)

{

memset(F,0,sizeof(F));

memset(A,0,sizeof(A));

read(n);

//printf("%d\n",n);

for(int i=1;i<=n;++i)

{

int k=0;char ch=getchar();

while(true)

{

if(ch<'0'||ch>'9'){

A[i][k]=1;

k=0;

}

if(ch<='9'&&ch>='0'){

k=(k<<1)+(k<<3)+(ch^48);

}

ch=getchar();

if(ch=='\n')break;

}

A[i][k]=1;

}

for(int i=1;i<=n;++i)

{

for(int j=1;j<=100;++j)

if(A[i][j])printf("%d ",j);

printf("\n");

}

F[0][0]=1;

for(int i=1;i<=100;++i)

{

for(int j=0;j<(1<<n);++j)

{

F[i][j]=F[i-1][j];

}

for(int j=1;j<=n;++j)

{

if(!A[j][i])continue;

for(int k=0;k<=(1<<n)-1;++k)

{

if(k&(1<<(j-1)))continue;

F[i][k+(1<<(j-1))]=(F[i][k+(1<<(j-1))] + F[i-1][k])%Mod;

}

for(int i=1;i<=100;++i)

{

for(int j=1;j<=(1<<n)-1;++j)

printf("%d ",F[i][j]);

printf("\n");

}

int tot=(1<<n)-1;

printf("%d\n",F[100][tot]);

}

fclose(stdin);

fclose(stdout);

return 0;

}

This entry was written by unclelu, posted on 十月 26, 2017 at 3:33 下午, filed under 状态压缩DP. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.

35 Trackbacks

By buy jordan 12 pinterest.com on 十一月 9, 2018 at 6:03 下午

buy jordan 12 pinterest.com

kd shoe line pinterest.comnike mercurial vapour 5 pinterest.comyeezy boost 350 boost v2 boost adidas yeezy boost 350 v2 350 boost v2 orange zebranike air max flair air942236 001
By blue ripped jeans on 十一月 11, 2018 at 1:50 下午

blue ripped jeans

adidas originals backpack for saleblue nike foams pinterest.comreal michael kors bag twitter.comnike tennis shorts
By womens tyler higbee 89 los angeles rams jersey on 十一月 11, 2018 at 7:10 下午

womens tyler higbee 89 los angeles rams jersey

ad adilette cf mono black s82229 summer beach sandals slippersnew air jordan 13 retro bred black true red white for salenike mercurial superfly v fg black total orangemiami heat lebron xi heat sport red metallic silver black
By cheetah nike running shoes womens pinterest.com on 十一月 11, 2018 at 9:16 下午

cheetah nike running shoes womens pinterest.com

nike elite javon wims 83 chicago bears jerseykids zach olstad 48 buffalo bills jerseykids zach olstad 48 buffalo bills jerseymens oakland raiders nike black vapor untouchable custom elite jersey
By nike air max 270 flyknit argentina ah8050 114 on 十一月 12, 2018 at 4:56 上午

nike air max 270 flyknit argentina ah8050 114

mizuno ignitus iii tf soccer cleats siver orange blackair jordan xxix bumble beepegasus33 nike ladies big size shoes air zoom pegasus 33 lilac grey core black off whiteair jordan hydro 5 white blue purple slide sandals
By kd 6 galaxy mint speckle 599424 002 on 十一月 12, 2018 at 5:38 上午

kd 6 galaxy mint speckle 599424 002

nike air jordan 11 red velvetwomens nike air zoom vomero 11 818010 500 dark purple black pinkadidas originals superstar white blue mens womens b27141 shoenike kyrie 4 black green red
By buy nike air max 2013 online on 十一月 12, 2018 at 9:45 下午

buy nike air max 2013 online

green adidas pants youtube.comnike low premium sboff white shirt blacknew balance 576 premium leather pack
By foot locker adidas originals on 十一月 13, 2018 at 8:03 上午

foot locker adidas originals

under armor jacketskobe black mamba shoesnike light brownnike strapback cap
By air max 90 baby pink tumblr.com on 十一月 13, 2018 at 7:26 下午

air max 90 baby pink tumblr.com

roshe run print floralkobe 10 x nikeid moonwalkerred and white nike free runnike air max zero 789695 001
By puma rs 0 gaming series error restart uk trainers on 十一月 13, 2018 at 7:27 下午

puma rs 0 gaming series error restart uk trainers

nike air max lb pink glaze uk trainersnike air force 1 fuchsia red uk trainersnike hyperdunk 2017 light tan uk trainersjordan cp3.xi sun glow uk trainers
By kd 7 christmas lucid green gorge green hyper crimson.png on 十一月 14, 2018 at 11:32 上午

kd 7 christmas lucid green gorge green hyper crimson.png

big and tall game robert foster 8 buffalo bills jerseypro line doug middleton 36 new york jets jerseykids game rashad greene 13 jacksonville jaguars jerseybaby limited sean lee 50 dallas cowboys jersey
By air jordan mens air jordan 31 low on 十一月 14, 2018 at 11:59 下午

air jordan mens air jordan 31 low

kids nike air jordansnba shoes lebron soldier 10nba jordan shoes air jordan 31asics asics pigskin
By marine grau herren nike shox deliver on 十一月 15, 2018 at 1:47 下午

marine grau herren nike shox deliver

jordan spizike boot dark cinder blackjordan jumpman pro 906876 010 black whitenike 849559 402 nike air max 2017adidas nmd xr1 pk zebra
By 2016 sparkly shoes nike crystal air pegasus 8330 on 十一月 17, 2018 at 12:27 下午

2016 sparkly shoes nike crystal air pegasus 8330

nike free 30 v6 womens nike free 30 v6nike free 30 v6 mens nike free 30 v6nike free 30 v6nike free 30 v5 womens nike free 30 v5
By 斜械谢褘泄 air jordan 22 on 十一月 17, 2018 at 8:13 下午

斜械谢褘泄 air jordan 22

褏邪泻懈褉芯蟹芯胁褘泄 nike air max woven卸械谢褌褘泄蟹械谢械薪褘泄 air jordan 18泻褉邪褋薪褘泄褎谢芯褌 nike craft mars yard ts nasa 2.0斜械谢褘泄锌褍褉锌褍褉薪褘泄 nike blazer mid vntg suede
By nike mercurial superfly v nike mercurial superfly v fg on 十一月 20, 2018 at 5:13 下午

nike mercurial superfly v nike mercurial superfly v fg

"adidas predator maniaadidas predator 184adidas predator 181adidas nemeziz tango 173"
By azul rosado nike zoom all out low 2.0 on 十一月 21, 2018 at 1:43 上午

azul rosado nike zoom all out low 2.0

beige gris roseonlycaqui negro nike air max lunar 90negro naranja nike magistax finale ii futsalnaranja voltio nike free run 4
By ben simmons tee on 十一月 21, 2018 at 11:29 下午

ben simmons tee

new baby sale twitter.comuk trainers adidas nmd r1 pk boost core black white cq2412vans gum black old skool twitter.comnike md runner 2 gpv twitter.com
By uk trainers womens nike air max invigor 95 customize on 十一月 22, 2018 at 1:55 上午

uk trainers womens nike air max invigor 95 customize

oro naranja new balance eva md 5zapatos adidas superstar metalblanco marr贸n nike odyssey reactrojo rosado nike air max moto 7
By 褏邪泻懈泻褉邪褋薪褘泄 converse wild skull canvas low on 十一月 22, 2018 at 8:21 下午

褏邪泻懈泻褉邪褋薪褘泄 converse wild skull canvas low

褎谢芯褌褉芯蟹芯胁褘泄 adidas aerobounce st锌褍褉锌褍褉薪褘泄芯褉邪薪卸械胁褘泄 adidas leopard泻褉邪褋薪褘泄芯褉邪薪卸械胁褘泄 nike kobe a.d ep蟹芯谢芯褌芯锌褍褉锌褍褉薪褘泄 nike air max flyknit
By orange grau vans off the wall leopard on 十一月 24, 2018 at 1:57 上午

orange grau vans off the wall leopard

lila gold converse dazzle colourbeige gelb jordan cp3 xirosa converse edison chen transparent bottomgr眉n gold lebron 15
By uk trainers grade school asics gelptg rainbow on 十一月 24, 2018 at 11:25 上午

uk trainers grade school asics gelptg rainbow

nike air huarache x ow olive yellownike zoom all out reddish orangenike magista orden fg bleached lilacua curry 3zero cinnamon
By uk trainers saint laurent sandals on 十一月 25, 2018 at 5:59 上午

uk trainers saint laurent sandals

uk trainers nike air max 270 flyknit white black racer blue total crimsonuk trainers air max guile collegiate navyuk trainers nike lebron 15 vivid pinkuk trainers nike air huarache run ultra chalk white
By lyser酶d sort mens nike shox rivalry on 十一月 25, 2018 at 9:25 上午

lyser酶d sort mens nike shox rivalry

r酶d nike shox classicbrun r酶d nike air zoom spiridon ultrakhaki gul nike sunray protect 2sort gul tennis
By orange grau nike air max tavas on 十一月 29, 2018 at 6:33 上午

orange grau nike air max tavas

air jordan vii 銉溿儷銉?銈般儸銉?/a>銈儑銈ｃ儉銈?arkyn 銉嶃偆銉撱兗銈枫儷銉愩兗銈儑銈ｃ儉銈?tubular shadow 銈兗銈?銉涖儻銈ゃ儓toms dot canvas 闈掋亜
By blinged out crystal crystal nike air max on 十二月 3, 2018 at 11:28 下午

blinged out crystal crystal nike air max

uk trainers nike shox rivalry brassinessuk trainers adidas ace 17.4 indoor olive greenuk trainers adidas nizza umberuk trainers air jordan cp3 xi carmine rose
By nike lunarepic low flyknit 2 915771 991 yahoo on 十二月 7, 2018 at 4:46 下午

nike lunarepic low flyknit 2 915771 991 yahoo

adidas tubular doom sock low s74925nike air max axis aa2146 101adidas originals urban backpack2018 new nike mercurial superfly 360 elite ag pro ah7377 810
By gongshow bucket hats canada twitter.com on 十二月 13, 2018 at 5:34 上午

gongshow bucket hats canada twitter.com

chanel red python bag twitter.compuma soft foam black twitter.comnike tiempo turf shoes twitter.combest boys trainers twitter.com
By lyst supreme on 十二月 13, 2018 at 11:06 上午

lyst supreme

胁芯谢褜褌褋械褉械斜褉褟薪褘泄 nike star runner tdv蟹芯谢芯褌芯褋械褉褘泄 nike air zoom mariah flyknit racer胁芯谢褜褌褋懈薪懈泄 nike archive 83褎谢芯褌泻褉邪褋薪褘泄 nike air huarache ultra
By 3d funny doge hoodies women men harajuku hoody jackets dogleopard 3d print animals galaxy hoodies on 十二月 14, 2018 at 9:23 上午

3d funny doge hoodies women men harajuku hoody jackets dogleopard 3d print animals galaxy hoodies

2018 off white pants virgil abloh sport jogger sweatpants jogging sweat pants pyrex version baseball pants pyrex version tutujianike spray jacket size s womens on carousellnike mens jordan 12 pullover hoodie black 819141 011devon cajuste game worn sign…
By alexander mcqueen x puma sodalite blue on 十二月 14, 2018 at 9:29 上午

alexander mcqueen x puma sodalite blue

saucony xodus iso womens 2014under armour boys infant engage 3 adjustable closure shoesreebok club c 85 indoor baseball grey blue white aq9874 16under armour hitch heavy 3 0 boot socks men
By long sleeve cotton tees womens coolibar on 十二月 15, 2018 at 6:22 上午

long sleeve cotton tees womens coolibar

g star saletall strappy gladiator sandalspharrell x adidas nmd human race tangerine orange black white bb3070iphone 6 case with water and glitter
By 褏邪泻懈褉芯蟹芯胁褘泄 nike roshe run metric on 十二月 15, 2018 at 11:33 上午

褏邪泻懈褉芯蟹芯胁褘泄 nike roshe run metric

vans slip sf slip sneakers womena477 export adidas jeremy scott js wings women shoes black white adidasnike hypervenom phantom 2 neymar x airvans classic slip shoes gum
By womens air jordan 6 retro black varsity red shoes on 十二月 16, 2018 at 8:02 上午

womens air jordan 6 retro black varsity red shoes

new mens puma evopower vigor 4 39 s indoor soccer shoes green gecko black safety yellow 103966 01functional roadsign georgie marron sandals mensvans golden coast black checkered skate shoesnike womens footwear elegant nike low top shoes ghost green gho…
By asos pleated shoulder lace midi dress on 十二月 16, 2018 at 8:11 上午

asos pleated shoulder lace midi dress

nike team football jerseyoff white ghfoshk whitemade italy cropped button down cotton shirt cropped button down cotton shirt womens shirtslyst pigalle cyrillic hoodie white for mennike power legend skinny womens trousers 833046

没有回路的路