首页 > 代码库 > SCOI2007排列perm

SCOI2007排列perm

2024-07-15 15:20:18   223人阅读

1072: [SCOI2007]排列perm

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 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

Sample Output

1
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.
View Code

 


联系
我们