首页 > 代码库 > SCOI2007排列perm
SCOI2007排列perm
1072: [SCOI2007]排列perm
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 805 Solved: 497
[Submit][Status]
Description
给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除(可以有前导0)。例如123434有90种排列能被2整除,其中末位为2的有30种,末位为4的有60种。
Input
输入第一行是一个整数T,表示测试数据的个数,以下每行一组s和d,中间用空格隔开。s保证只包含数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Output
每个数据仅一行,表示能被d整除的排列的个数。
Sample Input
7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29
Sample Output
1
3
3628800
90
3
6
1398
3
3628800
90
3
6
1398
HINT
在前三个例子中,排列分别有1, 3, 3628800种,它们都是1的倍数。 【限制】 20%的数据满足:s的长度不超过5, 1<=T<=5 50%的数据满足:s的长度不超过8 100%的数据满足:s的长度不超过10, 1<=d<=1000, 1<=T<=15,
Source
题解:
又一道恶心的状压DP,我对状压还不熟悉。。。
代码:
1 var f:array[0..10,0..1025,0..1025] of longint; 2 i,j,nn,k,m,t,l,ans,d,n:longint; 3 s,st:ansistring; 4 a,calc,c:array[0..1025] of longint; 5 b:array[0..10,0..1025] of longint; 6 procedure init; 7 begin 8 readln(s); 9 st:=copy(s,1,pos(‘ ‘,s)-1);10 n:=length(st);11 for i:=1 to n do a[i]:=ord(st[i])-ord(‘0‘);12 delete(s,1,pos(‘ ‘,s));13 val(s,d);//writeln(st,‘ ‘,d);14 fillchar(b,sizeof(b),0);15 for i:=0 to 1<<n-1 do16 begin17 j:=i;calc[i]:=0;18 while j<>0 do19 begin20 inc(calc[i]);dec(j,j and (-j));21 end;22 j:=calc[i];23 inc(b[j,0]);b[j,b[j,0]]:=i;24 end;25 end;26 procedure main;27 begin28 fillchar(f,sizeof(f),0);29 for i:=1 to n do f[1,1<<(i-1),a[i] mod d]:=1;30 for i:=2 to n do31 for l:=1 to b[i,0] do32 begin33 j:=b[i,l];34 for k:=1 to n do35 if j and (1<<(k-1))<>0 then36 for m:=0 to d-1 do37 inc(f[i,j,(10*m+a[k]) mod d],f[i-1,j-1<<(k-1),m]);38 end;39 ans:=f[n,1<<n-1,0];40 fillchar(c,sizeof(c),0);41 for i:=1 to n do inc(c[a[i]]);42 for i:=0 to 9 do43 if c[i]<=1 then continue44 else for j:=2 to c[i] do ans:=ans div j;45 writeln(ans);46 end;47 48 begin49 assign(input,‘input.txt‘);assign(output,‘output.txt‘);50 reset(input);rewrite(output);51 readln(t);52 while t>0 do53 begin54 dec(t);55 init;56 main;57 end;58 close(input);close(output);59 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。