题目描述
finally, you got into the cellar of your preferred brewery where you expected many large piles of beer barrels to be stored. You are eager to inspect the barrels and maybe even their content (a lot and lot of content, actually...). Unfortunately, you find only five barrels, all hopelessly empty and dry. Some numbers are painted on the first four barrels, one number on each of them. A note is attached to the fifth barrel. Behind the barrels in the dark, there is some low and barely discernible door in the wall, leading quite obviously to another lower cellar where you hope a whole slew of full barrels is kept hidden. The door is locked with a heavy and complex looking lock. With no obvious further constructive action in mind, you sit down to study the note on the fifth barrel. Its essence is the following. Denote the numbers painted on the first, second, third and fourth barrel by A, B, K and C. Numbers A, B and C are just single digits. Now imagine that in the distant future some incredibly powerful computer (powered by quantum yeast) prints a list of all numbers which have exactly K digits and in which each digit is equal to A or B. Another equally mighty computer then takes the list and also the value C as the input and calculates the number of occurrences of digit C in the whole list. The resulting number taken modulo 1 000 000 007 is to be typed into the door lock to open it and to gain access to the lower cellar. You decide to calculate that number in your notebook you took with you.
输入
The input consists of a single line with four integers A, B, K, C (1 ≤ A, B, C ≤ 9, 0 ≤ K ≤ 1000)which represent the numbers painted on the first four barrels.
输出
Output a single integer which opens the door lock.
样例输入 Copy
1 2 3 2样例输出 Copy
12 #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; const ll mod=1000000007; int A,B,C,K; ll ls,jg; ll ksm(int a,ll b,ll mod) { ll ans=1; while(b) { if(b&1) ans=(ans%mod*a%mod)%mod; a=(a%mod*a%mod)%mod; b>>=1; } return ans; } ll plzh(int n,int m) { ll ans=1; int ls=m; while(ls) { ans=(ans%mod*n%mod)%mod; n--; ls--; } return ans; } int main() { cin>>A>>B>>K>>C; if(C!=A&&C!=B) cout<<0<<endl; else if(A==B) cout<<K<<endl; else { for(int i=1; i<=K; i++) { ls=(i%mod*plzh(K,i)%mod*ksm(plzh(i,i),mod-2,mod)%mod)%mod; jg=(jg%mod+ls)%mod; } cout<<jg<<endl; } return 0; }首先C与A，B都不想相等时，个数无论怎么排都是0
其次，A与B相等时，就只有一种排法，即全为A（或B），K是几位数就有多少个。
然后就是排列组合了，总共这K位数就包含两个数字，可得公式算出这样的K位数有多少个：C(K,1)+C(K,2)+C(K,3)+...+C(K,K)
个数就是每个对应的组合数乘以个数即可（可能说的不清楚，我也不知道怎么说）:C(K,1)*1+C(K,2)*2+C(K,3)*3+...+C(K,K)*K
其中求C(n,m)转换为：C(n,m)=A(n,m)/A(m,m);注意这里有除法了，题目中要mod一个数，别忘了逆元
