A lightoj1214 (取模)
非常简单，每一位表示一下模一下，秒了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
char str[999];
int main(){
int T;scanf("%d",&T);
for(int x=1;x<=T;++x){
ll m,ans=0;
printf("Case %d:",x);
scanf("%s%lld",str,&m);
int len=strlen(str);
for(ll i=len-1,wei=1;i>=0;--i){
if(str[i]=='-') continue;
ll now,k=str[i]-'0';
now=(((wei)%m)*(k%m))%m;
ans=(ans+now)%m;
wei=(wei*10)%m;
}
if(ans%m) printf(" not divisible\n");
else printf(" divisible\n");
}
return 0;
}
|
B hdu2197 思维题
由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。
很显然非本原串更好求，可以用总数-非本串个数，怎么减呢。感觉肯定是需要用到之前的答案对吧(类似于递推)。实际上不就是找循环节么。它的每个循环节的长度就是它的长度的因数对吧。假设n=8，它的因数有1,2,4.
先看1，{1/1/1/1/1/1/1/1}和{0/0/0/0/0/0/0/0} 减去。
看2：{11/11/11/11},{00/00/00/00},{10/10/10/10},{01/01/01/01}.
很显然后两个{01}和{10}也是2的本原串。一起减掉4？然而和1有重复对吧.因为我们是从小到大看的，而前两个可以在1的时候减掉，所以，只要减掉后两个，也就是2的本原串个数就行了。对于它的非本原串来说，它们一定能有循环节更小的表示方法，而那些我们肯定在之前已经减过了。4也是同理。所以只要从小到大减去每个因子的本原串个数就行了，因为它们是不可再分的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
map<ll,ll> p;
typedef map<ll,ll>::iterator it;
const ll mod = 2008;
ll pow2(ll a,ll b)
{
ll ans=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) ans=ans*a%mod;
return ans;
}
ll solve(ll n)
{
if(p.count(n)) return p[n];
ll ans=pow2(2LL,n);
for(ll i=1;i*i<=n;++i)
{
if(n%i==0){
ans=(ans-solve(i)+mod)%mod;
if(i*i<n&&i>1)
ans=(ans-solve(n/i)+mod)%mod;
}
}
p[n]=ans;
return ans;
}
int main()
{
p[0]=0,p[1]=2,p[2]=2;
ll n;
while(~scanf("%lld",&n))
{
printf("%lld\n",solve(n));
}
return 0;
}
|
C
D hdu5019
对gcd分解因子，然后排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+100;
const ll inf = 1e13;
vector<ll> v;
inline ll fast_pow(ll a,ll b){
ll ans=1;
for(;b;b>>=1,a*=a){
if(b&1) ans*=a;
}
return ans;
}
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
void factor(ll n){
for(ll i=2;i*i<=n;++i){
if(n%i==0){
v.push_back(i);
if(i*i<n) v.push_back(n/i);
}
}
v.push_back(n);if(n!=1) v.push_back(1);
}
int main(){
int T;scanf("%d",&T);
while(T--){
v.clear();
ll a,b,k;scanf("%lld%lld%lld",&a,&b,&k);
ll g=gcd(max(a,b),min(a,b));
factor(g);
sort(v.begin(),v.end());
ll sz=v.size()-k;
if(sz>=0LL) printf("%lld\n",v[sz]);
else printf("-1\n");
}
return 0;
}
|
E hdu4549 (矩阵快速幂 费马小定理)
首先看题，显然F[n]=b^(f(n))*a^(f(n-1))%mod,f(n)表示斐波那契数列(f(1)=f(2)=1)
然后肯定要用矩阵快速幂求对吧。构建矩阵快速幂的矩阵：{ {1,1},{1,0} } (并不会用latex之类的…)
注意快速幂时还要有一个单位矩阵，是{ {1,0},{0,1} }
因为一开始忘了矩阵乘法的乘法顺序所以自己定义了一下，不过好像反了(逃)。以及矩阵乘法里懒得写第三层循环直接枚举元素…总之代码里透露着各种不规范…
然而1e9的斐波那契数列早大到不知哪里去了，于是用费马小定理。快速的说就是a^b%mod==a^(b%(mod-1))%mod.
为什么？根据费马小定理可以知道x^(p-1)%p=1,设x等于a^b,原式等价于a^(b*(p-1))%p=a^(0).
此时可以看出b*(p-1)这个是有p-1的因子的a的幂，而且原式%p之后幂就变成了0，这不就相当于b*(p-1)%(p-1)么…
所以在矩阵快速幂里%(mod-1)就行了…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <cstdio>
#include <algorithm>
#include <vector>
typedef long long ll;
const ll mod = 1000000007;
struct cb4{
ll c[2][2];
};
inline cb4 mult(cb4 a,cb4 b){
cb4 ans;
for(int i=0;i<2;++i){
for(int j=0;j<2;++j)
ans.c[i][j]=((a.c[0][i]%(mod-1))*(b.c[j][0]%(mod-1))%(mod-1)
+(a.c[1][i]%(mod-1))*(b.c[j][1]%(mod-1))%(mod-1))%(mod-1);
}
return ans;
}
const cb4 std_cb=(cb4){{{1,0},{0,1}}};
const cb4 fp_cb=(cb4){{{1,1},{1,0}}};
cb4 fast_pow(cb4 a,ll b){
cb4 ans=std_cb;
for(;b;b>>=1,a=mult(a,a)){
if(b&1) ans=mult(ans,a);
}
return ans;
}
ll fast_pow(ll a,ll b){
ll ans=1;a%=mod;
for(;b;b>>=1,a=(a*a)%mod){
if(b&1) ans=ans*a%mod;
}
return ans;
}
int main()
{
ll a,b,n;
while(~scanf("%lld%lld%lld",&a,&b,&n)){
cb4 ai={{{1,0},{0,0}}};
if(n==0) printf("%lld\n",a);
else if(n==1) printf("%lld\n",b);
else{
cb4 fei=mult(ai,fast_pow(fp_cb,n-1));
printf("%lld\n",fast_pow(b,fei.c[0][0]%mod)*fast_pow(a,fei.c[0][1])%mod);
}
}
return 0;
}
|
最后：矩阵快速幂时间复杂度n^3log(n)
F cf450b 矩阵快速幂
矩阵快速幂模板题。把矩阵快速幂的矩阵改成 { {1,-1},{1,0} } 就行了。
不过要注意，如果是负数，要%成正的.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <cstdio>
#include <algorithm>
#include <vector>
typedef long long ll;
const ll mod = 1000000007;
struct cb4{
ll c[2][2];
};
inline cb4 mult(cb4 a,cb4 b){
cb4 ans;
for(int i=0;i<2;++i){
for(int j=0;j<2;++j)
{
ans.c[i][j]=((a.c[0][j]%(mod))*(b.c[i][0]%(mod))%(mod)
+(a.c[1][j]%(mod))*(b.c[i][1]%(mod))%(mod))%(mod);
while(ans.c[i][j]<0)
ans.c[i][j]=(ans.c[i][j]+mod)%mod;
}
}
return ans;
}
const cb4 std_cb=(cb4){{{1,0},{0,1}}};
const cb4 fp_cb=(cb4){{{1,-1},{1,0}}};
cb4 fast_pow(cb4 a,ll b){
cb4 ans=std_cb;
for(;b;b>>=1,a=mult(a,a)){
if(b&1) ans=mult(a,ans);
}
return ans;
}
ll fast_pow(ll a,ll b){
ll ans=1;a%=mod;
for(;b;b>>=1,a=(a*a)%mod){
if(b&1) ans=ans*a%mod;
}
return ans;
}
int main()
{
ll a,b,n;
scanf("%lld%lld%lld",&a,&b,&n);
cb4 ai={{{b,0},{a,0}}};
if(n==1) printf("%lld\n",(a+mod)%mod);
else{
cb4 fei=mult(ai,fast_pow(fp_cb,n-2));
ll ans=fei.c[0][0];
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
|
G hdu5651 排列组合
给一个串，看能组成几个回文串。
首先统计一下每个字母的个数。如果有多个字母的个数为奇数的数量>1，那没法回文。因为如果只有一个字母的个数为奇数，那么放到中间就行啦。
如果可以，那么就能回文，然后只要找出其中一半有多少种组成就行了。问题转化为算一下带有重复元素的全排列。公式:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll Getaii(ll n)
{
ll ans=1;
for(ll i=1;i<=n;++i) ans=ans*i%mod;
return ans;
}
ll fast_pow(ll a,ll b)
{
ll ans=1;
for(;b;b>>=1,a=a*a%mod)
{
if(b&1) ans=ans*a%mod;
}
return ans;
}
int main()
{
int T;scanf("%d",&T);
while(T--){
ll sz[26]={0};
char ch;
while((ch=getchar())<'a'||ch>'z');
while(ch>='a'&&ch<='z') ++sz[ch-'a'],ch=getchar();
ll cnt=0,tot=0;
for(int i=0;i<26;tot+=sz[i],++i) if(sz[i]%2) ++cnt;
if(cnt>1) {printf("0\n");continue;}
ll ans=Getaii(tot/2);
for(int i=0;i<26;++i){
if(sz[i]==0) continue;
ans=ans*fast_pow(Getaii(sz[i]/2),mod-2LL)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
|
H hdu2200 排列组合
因为之前没读题，所以请好好读读题目：
Eddy是个ACMer,他不仅喜欢做ACM题,而且对于Ranklist中每个人的ac数量也有一定的研究,
他在无聊时经常在纸上把Ranklist上每个人的ac题目的数量摘录下来，然后从中选择一部分人(或者全部)按照ac的数量分成两组进行比较，
他想使第一组中的最小ac数大于第二组中的最大ac数，但是这样的情况会有很多，聪明的你知道这样的情况有多少种吗?
从中选择一部分人，所以是C(n,k), 使第一组中的最小ac数大于第二组中的最大ac数，所以只要在序列里切一刀就行了(k-1).所以这个题就看你会不会求组合数就行了。
注意这个组合数非递推的求法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll C(ll n,ll a){
ll ans=1;
for(ll i=1;i<=a;++i)
ans=ans*(n-i+1)/i;
return ans;
}
int main()
{
ll n;
while(~scanf("%lld",&n)){
ll ans=0;
for(ll i=1;i<=n;++i){
ans+=C(n,i)*(i-1);
}
printf("%lld\n",ans);
}
return 0;
}
|
I hdu1465 排列组合
错排公式模板题
错排公式：每个都恰好不对的所有可能情况
D(i)=(i-1)*(d(i-1)+d(i-2)) D(1)=0,D(2)=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[30]={0,0,1};
ll C[30][30];
int main()
{
for(ll i=3;i<=20;++i) a[i]=(i-1)*(a[i-1]+a[i-2]);
ll n;
while(~scanf("%lld",&n)){
printf("%lld\n",a[n]);
}
return 0;
}
|
J hdu1796 容斥定理
类似于noip初赛的某道题：1～n中不能被2,3,5整除的数有多少个。考点当然是容斥定理。
首先算出能整除的，然后用总数减掉。具体请看代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
int main()
{
ll n,m;
while(~scanf("%lld%lld",&n,&m))
{
ll ans=0;
vector<ll> v;
for(int i=1;i<=m;++i) {ll t;scanf("%lld",&t);if(t>0) v.push_back(t);}
m=v.size();
for(ll i=1;i<(1LL<<m);++i)
{
ll x=1;
int cnt=0;
for(ll j=0;j<m;++j){
if((i>>j)&1LL){
++cnt;x=x*v[j]/gcd(x,v[j]);
}
}
if(cnt%2==1) ans+=(n-1)/x;
else ans-=(n-1)/x;
}
printf("%lld\n",ans);
}
return 0;
}
|
