2015 Multi-University Training Contest 6 hdu 5362 Just A String
Just A String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 643 Accepted Submission(s): 182
Problem Description
soda has a random string of length n which is generated by the following algorithm: each of n characters of the string is equiprobably chosen from the alphabet of size m.
For a string s, if we can reorder the letters in string s so as to get a palindrome, then we call s a good string.
soda wants to know the expected number of good substrings in the random string.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers $n and m (1 \leq n,m \leq 2000)$.
Output
For each case, if the expected number is E, a single integer denotes$ E\dot mn mod 1000000007$.
Sample Input
3
2 2
3 2
10 3
Sample Output
10
40
1908021
Author
zimpha@zju
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = ;
const int mod = ;
long long dp[maxn][maxn],PM[maxn];
int main() {
PM[] = dp[][] = ;
int kase,n,m;
scanf("%d",&kase);
while(kase--) {
scanf("%d%d",&n,&m);
dp[][] = m;
for(int i = ; i <= n; ++i) PM[i] = PM[i-]*m%mod;
for(int i = ; i <= n; ++i) {
for(int j = , k = min(i,m); j <= k; ++j) {
dp[i][j] = ;
if(j) dp[i][j] += dp[i-][j-]*(m - j + );
if(j + <= min(i - ,k)) dp[i][j] += dp[i-][j+]*(j + );
dp[i][j] %= mod;
}
}
long long ret = ;
for(int i = ; i <= n; ++i)
ret += dp[i][i&]*(n - i + )%mod*PM[n-i]%mod;
printf("%I64d\n",ret%mod);
}
return ;
}
最新文章
- linux系统免密码登陆
- mongodb版本特性
- 【MySQL】MySQL 5.7 sys Schema
- Kali Linux Web 渗透测试视频教程— 第四课 google hack 实战
- Ubuntu学习笔记-win7&;Ubuntu双系统简单搭建系统指南
- Oralce新建数据库、新建远程登录用户全过程
- iOS 数组字典操作
- Cglib及其基本使用
- Joone
- MyBatis3系列__04CRUD以及参数处理
- one-hot编码
- Java开发环境配置(Jdk、Tomcat、eclipse)
- Django 中间件 请求前
- Elasticsearch学习笔记——分词
- poj 3320(尺取法)
- bzoj5312: 冒险(势能均摊线段树)
- 机器学习ML策略
- String.format的用法
- poj 3278 Catch That Cow(bfs+队列)
- 各版本.NET委托的写法回顾(转)