14261. Generating WordsConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
Given two words A and B, a word W is said to be good if it satisfies the following conditions simultaneously.
1) All letters in W are also in A.
2) No letter in W is in B.
3) W contains N letters.
Given N, A and B, your task is to find out how many different good words exist.
Input
The input begins with a line containing an integer T (T<=50), which indicates the number of test cases. The following T lines each contain an integer N (1<=N<=10000), and two words A and B. A and B only contain lowercase English letters. The length of each word will not exceed 50.
Output
For each case, output the number of different good words in a line. The answer may be very large, so just output the remainder of the answer after divided by 1007.
Sample Input33 lby myf1 ddfg ffgd5 lby yglSample Output801Hint
For the first test case, you can generate 8 good words: lll, llb, lbl, lbb, bll, blb, bbl, bbb.
Problem Source
SYSUCPC 2014 Preliminary (Online) Round
#include <iostream>#include <string>using namespace std;int main() {std::ios::sync_with_stdio(false);int caseNum;cin >> caseNum;while (caseNum–) {int n, m = 0, ans = 1;string a, b;cin >> n >> a >> b;bool isOK['z' + 1];for (int i = 'a'; i <= 'z'; i++) isOK[i] = false;for (int i = a.size() – 1; i >= 0; i–) isOK[a[i]] = true;for (int i = b.size() – 1; i >= 0; i–) isOK[b[i]] = false;for (int i = 'a'; i <= 'z'; i++) if (isOK[i]) m++;for (int i = 0; i < n; i++, ans %= 1007) ans *= m;cout << ans << endl;}return 0;}
,人若勇敢就是自己最好的朋友