[BZOJ1072][SCOI2007]排列perm

試題描述

給一個數字串s和正整數d, 統計s有多少種不同的排列能被d整除（可以有前導0）。例如123434有90種排列能被2整除，其中末位為2的有30種，末位為4的有60種。

輸入

輸入第一行是一個整數T，表示測試數據的個數，以下每行一組s和d，中間用空格隔開。s保證只包含數字0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

輸出

每個數據僅一行，表示能被d整除的排列的個數。

輸入示例

7 000 1 001 1 1234567890 1 123434 2 1234 7 12345 17 12345678 29

輸出示例

1 3 3628800 90 3 6 1398

數據規模及約定

100%的數據滿足：s的長度不超過10, 1<=d<=1000, 1<=T<=15

題解

設 f(S, i) 表示選擇了位置集合 S 的數，得到的排列對 mod d = i，這時的方案數。轉移的時候注意每種數字只能轉移一次，我們不妨選擇每種數字最靠前出現的還沒有選擇的位置。

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std;const int BufferSize = 1 << 16; char buffer[BufferSize], *Head, *Tail; inline char Getchar() {if(Head == Tail) {int l = fread(buffer, 1, BufferSize, stdin);Tail = (Head = buffer) + l;}return *Head++; } int read() {int x = 0, f = 1; char c = Getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }return x * f; }#define maxs 1024 #define maxm 1000int f[maxs][maxm], num[10];int main() {int T = read();while(T--) {int n = 0, d;char ch = Getchar();while(!isdigit(ch)) ch = Getchar();while(isdigit(ch)) num[n++] = ch - '0', ch = Getchar();d = read();memset(f, 0, sizeof(f));f[0][0] = 1;int all = (1 << n) - 1;for(int S = 0; S <= all; S++)for(int i = 0; i < d; i++) if(f[S][i]) {bool tag[10]; memset(tag, 0, sizeof(tag));for(int j = 0; j < n; j++) if(!(S >> j & 1) && !tag[num[j]])f[S|(1<<j)][(i*10+num[j])%d] += f[S][i], tag[num[j]] = 1;}printf("%d\n", f[all][0]);}return 0; }

?

轉載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/6938474.html

總結

以上是生活随笔為你收集整理的[BZOJ1072][SCOI2007]排列perm的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。