Given an array with
n
integers, assume f(S) as the result of executing xor operation among all the elements of set S. e.g. if S={1,2,3} then f(S)=0.
your task is: calculate xor of all f(s), here s⊆S.
This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, the first line contains a single integer number
n(1≤n≤1,000) that represents the size of the given set. then the
following line consists of n different integer numbers indicate
elements(≤109) of the given set.
For each test case, print a single integer as the answer.
1
3
1 2 3
0
In the sample，S
, subsets of S are: ∅
, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
给你一个集合S，然后定义F(s)表示这个集合所有元素的异或和。
然后求所有S的子集的F(s)的异或和
考虑每个数的贡献，显然当n>1的时候，每个数在2^(n-1)个集合里面，所以贡献为0
当n=1的时候，答案就是x啦
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 #include<map> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 const int maxn = 1e5; 11 typedef long long ll; 12 void input(){ 13 int t,n; 14 scanf("%d",&t); 15 while(t--){ 16 scanf("%d",&n); 17 int x; 18 scanf("%d",&x); 19 for(int i = 2; i<=n; i++){ 20 scanf("%d",&x); 21 } 22 if(n == 1){ 23 printf("%d\n",x); 24 } 25 else{ 26 printf("0\n"); 27 } 28 } 29 } 30 int main() 31 { 32 input(); 33 return 0; 34 }
As we all known, xiaoxin is a brilliant coder. He knew palindromic strings when he was only a six grade student at elementry school.
This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin‘s leader needs to buy?
This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, there is a single line containing a string S(1≤length(S)≤1,000).
For each test case, print an integer which is the number of watermelon candies xiaoxin‘s leader needs to buy after mod 1,000,000,007.
3
aa
aabb
a
1
2
1
给你一个串，你可以改变字符位置
问你能够形成多少种回文串。
高中一个元素中有重复的，A(n)/A(a1)/A(a2)……，还学习了个逆元问题
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 #include<map> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 const int mod = 1e9+7; 11 typedef long long ll; 12 char s[1111]; 13 int a[30]; 14 ll quick_pow(ll a, ll b) { 15 ll ans = 1; 16 for (; b; b /= 2, a = (a * a) % mod) 17 if (b & 1) ans = (ans * a) % mod; 18 return ans; 19 } 20 21 ll A(ll n){ 22 ll sum = 1; 23 for(long long i = 1; i<=n; i++){ 24 sum = (i*sum)%mod; 25 } 26 return sum; 27 } 28 void input(){ 29 int t; 30 scanf("%d",&t); 31 while(t--){ 32 scanf("%s",s); 33 memset(a,0,sizeof(a)); 34 int len = strlen(s); 35 for(int i = 0; i<len; i++){ 36 a[s[i]-‘a‘+1]++; 37 } 38 int count = 0; 39 ll sum = 0; 40 for(int i = 1; i<=26; i++){ 41 if(a[i]%2 == 1) count++; 42 a[i]/=2; 43 sum += a[i]; 44 } 45 46 if(count>1) printf("0\n"); 47 else{ 48 sum = A(sum); 49 for(int i = 1; i<=26; i++){ 50 sum = sum * quick_pow(A(a[i]), mod - 2) % mod; 51 } 52 printf("%I64d\n",sum); 53 } 54 } 55 } 56 int main() 57 { 58 input(); 59 return 0; 60 }
原文：http://www.cnblogs.com/littlepear/p/5327388.html
