- 1004-构造
- 1005-数学乱搞-费马小定理降幂-卡常
- 1009-思维题
1004 Distinct Sub-palindromes
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6754
签到构造题qwq
n>3的话构造abcabcabc……的序列即可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
using namespace std;
int m,n;
int main()
{
int i,j,t;
int ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(n==1)
ans=26;
else if(n==2)
ans=676;
else if(n==3)
ans=26*26*26;
else
ans=25*24*26;
printf("%d\n",ans);
}
return 0;
}1005 Fibonacci Sum
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6755题意：
$F_n$为斐波那契序列已知N,C,K，求：输入T组样立，分别输入N,C,K，输出上式模1e9+9
数据范围：$1≤T≤200,1≤N,C≤10^{18},1≤K≤10^5$输入
2
5 1 1
2 1 2输出
12
2思路
数据大，考虑斐波那契通项公式令于是有然后用等比数列通项求一下就行，注意考虑公比为0的情况QAQ。。。。
可以用O(k)的复杂度进行计算
再处理根号五的问题。由于答案模1e9+9，想到二次剩余
$x^2\equiv5(mod 1e9+9)$
解出来x为383008016
然后这题还要用费马小定理降幂，降低时间复杂度QAQc%=(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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
typedef long long ll;
const ll qaq=383008016;
const ll mod=1e9+9;
ll ai[100005],bi[100005];
ll Fact[100005],INV[100005];
inline ll ksm(ll a,ll k){
ll ans=1;
while(k){
if(k&1ll) ans=ans*a%mod;
a=a*a%mod;
k>>=1ll;
}
return ans%mod;
}
inline ll inv(ll a){
return ksm(a,mod-2);
}
inline void init(ll n){
Fact[1]=1;Fact[0]=1;
for(ll i=2;i<=n;++i) Fact[i]=Fact[i-1]*i%mod;
INV[n]=ksm(Fact[n],mod-2);
for(ll i=n-1;i>=0;--i) INV[i]=INV[i+1]*(i+1)%mod;
}
int main(){
init(100001);
ll t;scanf("%lld",&t);
ll a=(1+qaq)*inv(2)%mod;
ll b=((1-qaq)+mod)*inv(2)%mod;
ai[0]=1,bi[0]=1;
for(int i=1;i<=100000;i++) ai[i]=ai[i-1]*a,ai[i]%=mod;
for(int i=1;i<=100000;i++) bi[i]=bi[i-1]*b,bi[i]%=mod;
ll qaqaq=inv(qaq);
ll op;
while(t--){
ll n,c,k;scanf("%lld%lld%lld",&n,&c,&k);
c%=(mod-1);
ll ans=0;
if(k&1ll) op=-1;
else op=1;
for(ll i=0;i<=k;i++){
ll temp=(ai[i]*bi[k-i])%mod;
ll tempp=ksm(temp,c);
temp=(tempp*(ksm(tempp,n)-1))%mod;
temp*=inv(tempp-1);
temp%=mod;
if(tempp==1) temp=n%mod;
temp=temp*Fact[k]%mod*INV[i]%mod*INV[k-i]%mod;
ans=ans+temp*op+mod;
ans%=mod;
op*=-1;
}
ans*=ksm(qaqaq,k);
ans=ans%mod;
printf("%lld\n",ans);
}
return 0;
}1009 Leading Robots
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6759
嫖份队友代码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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
struct node
{
long long int p,a;
}ro[500005];
struct stac{
long long int p;
long long int a;
bool flag;//可不可能成为第一名
}sta[500005];
bool cmp(node a,node b){
if(a.p==b.p) return a.a>b.a;
else return a.p>b.p;
}
int ans[500005];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld%lld",&ro[i].p,&ro[i].a);
}
sort(ro,ro+n,cmp);
int num=1;
sta[1].p=ro[0].p;
sta[1].a=ro[0].a;
sta[1].flag=1;;
for(int i=1;i<n;i++){
if(ro[i].p<sta[num].p&&ro[i].a>sta[num].a){
++num;
sta[num].p=ro[i].p;
sta[num].a=ro[i].a;
sta[num].flag=1;
}
else if(ro[i].p==sta[num].p&&ro[i].a==sta[num].a)
{
sta[num].flag=0;//这个人不可能成为第一名
}
}
if(num==1){
if(sta[num].flag) printf("1\n");
else printf("0\n");
continue;
}
int nn=2;
ans[1]=1;
ans[2]=2;
for(int i=2;i<=num;i++){
do{
long long int p1=(sta[ans[nn]].p-sta[i].p)*(sta[ans[nn]].a-sta[ans[nn-1]].a);
long long int p2=(sta[ans[nn-1]].p-sta[ans[nn]].p)*(sta[i].a-sta[ans[nn]].a);
if(p1<=p2) nn--;
else break;
}
while(nn>=2);
++nn;
ans[nn]=i;
}
int Ans=0;
for(int i=1;i<=nn;i++){
// printf("%d\b",ans[i]);
if(sta[ans[i]].flag) Ans++;
}
printf("%d\n",Ans);
}
return 0;
}