CodeForces 150B- Quantity of Strings 推算..
假设 k = 5 , n>k , (1,2,3,4,5) -> 1=5,2=4,3任意
(2,3,4,5,6) -> 2=6,3=5,4任意...综合上面的可得出1=3=5,2=4=6
(3,4,5,6,7) -> 3=7,4=6,5任意...综合上面的可得出1=3=5=7,2=4=6
....... 综上可得..奇数位的数应该相同,偶数位的数应该相同
再假设k = 4, n>k (1,2,3,4) - >1=4,2=3
(2,3,4,5) - > 2=5,3=4...综合上面的可得出1=2=3=4=5
(3,4,5,6) -> 3=6,4=5...综合上面的可得出 1=2=3=4=5=6
....... 综上所得..所有的数必须相同
大致的思路有了...但是要注意几个特殊的情况.. 这些情况的造成是因为没有有交集的回文串..不能上下综合得出条件..
例如...k=1的时候..回文串都是独立的....总数是m^n
k=n的时候..回文串只有一个..当然也是独立的...总数是m^((n+1)/2)
k>n的时候...串可以任意了.m^n....我觉得这个数据有些无聊..
Program:
#include<iostream> #include<stack> #include<queue> #include<stdio.h> #include<algorithm> #include<string.h> #include<cmath> #define ll long long #define oo 1000000007 #define MAXN 100005 using namespace std; int n,m,k; int POW(ll m,ll n) { int i; ll ans=1; for (i=1;i<=n;i++) ans=(ans*m)%oo; return (int)ans; } int main() { while (~scanf("%d%d%d",&n,&m,&k)) { if (k>n || k==1) printf("%d\n",POW(m,n)); else if (k==n) printf("%d\n",POW(m,(k+1)/2)); else if (k%2) printf("%d\n",m*m); else printf("%d\n",m); } return 0; }
相关文章
- Twitter OA prepare: Equilibrium index of an array
- POJ 3083:Children of the Candy Corn(DFS+BFS)
- Ajax request returns 200 OK, but an error event is fired instead of success
- Types of Entity in Entity Framework:
- container_of宏
- 解决RocketMQ报No route info of this topic:异常
- git提交失败running pre-commit hook: lint-staged [33m[33m‼[33m Some of your tasks use `git add` command
- 职责链模式(Chain of Responsibility)
- CodeForces Gym 100685E Epic Fail of a Genie (贪心,控制精度)
- CodeForces 702B Powers of Two (暴力,优化)
- The promises and challenges of std::async task-based parallelism in C++11 C++11 std::async/future/promise
- 论文阅读:Transferring skills to humanoid robots by extracting semantic representations from observations of human activities
- error adding seccomp filter rule for syscall bdflush : requested action matches default action of filter
- HDU 3080 The plan of city rebuild(prim和kruskal)
- poj1236 Network of Schools ,有向图求强连通分量(Tarjan算法),缩点
- Codeforces Round #234 (Div. 2):B. Inna and New Matrix of Candies
- [CareerCup] 11.8 The Rank of Number 数的排行
- 解决Typora过期报错:This beta version of Typora is expired, please download and install a newer vsersion
- gzip: stdin: unexpected end of file tar: 归档文件中异常的 EOF
- 349. Intersection of Two Arrays
- Java 报错No enclosing instance of type E is accessible. Must qualify the allocation with an enclosing