[BZOJ1072][SCOI2007]排列perm

[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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。