题目传送门：http://codeforces.com/contest/889/problem/C
题目大意：有一个函数，传一个长度为n的数组a进去，并设计一个参数k，它会用以下方式帮你找最大值：从左往右扫a，并记录当前最大值。如果变更完当前最大值之后，再扫连续的k个元素，当前最大值都没有变（或者扫完了a），它就会直接返回当前最大值。现在给定n,k，你要输出有多少个1~n的排列a，会使得这个函数不返回n。 n,k<=106 。
题目分析：这题想了我一个下午+半个晚上。当我最终灵光一现想到解法，并把那短短的几行代码码完AC的时候，我想起了一句诗：“两句三年得，一吟双泪流”。（也许我的DP还是太菜了）
这题很明显是DP，但主要问题是怎么记状态。如果我们记长度为一维，最大值放在哪里（或者统计答案的时候能扫到a数组的哪里）为另一维，显然已经超时。对此，我们需要对状态做一些约束，最后用组合数学来帮忙计算答案。
设f[i]表示1~i的排列中，i放在最后一位，且最终返回值为i的方案数。很明显，i-1放的位置应该是i-k~i-1。假设我们已经枚举了i-1放在i-x这个位置，那么就有下图：
文章图片
其中绿色部分是一个子问题，红色部分可以自由组合。由于{2 5 6 8}和{1 2 3 4}是等价的，所以左边的方案数为 f[i?x?1]?Ci?x?1i?2 。而左边重编号之后，右边可以自由组合，所以右边的贡献是 (x?1)! 。这样就有：
f[i]=∑x=i?ki?1f[i?x?1]?Ci?x?1i?2?(x?1)!
然而这个是不可以再优化的。于是我们不妨记 g[i]=f[i]i! ，这样 f[i?x?1]?Ci?x?1i?2?(x?1)! 就变成了 g[i?x?1]?(i?2)! 。然后对g做个部分和即可。
最终输出答案的时候，可以枚举一下n放在了哪个位置（假设在第i位），那么方案数就是 f[i]?(n?1)! 。然后用总方案数减去合法的方案数，即可算出不合法的方案数。
预处理阶乘和线性逆元，时间就是 O(n) 的。
【数论|Codeforces Round #445 Div1 C（Maximum Element （组合数学+DP））】CODE：
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000100;
const long long M=1000000007;
typedef long long LL;
LL f[maxn];
LL fac[maxn];
LL rev[maxn];
int n,k;
LL ans=0;
int main()
{
freopen("2329.in","r",stdin);
freopen("2329.out","w",stdout);
scanf("%d%d",&n,&k);
fac[0]=1;
for (int i=1;
i<=n;
i++) fac[i]=fac[i-1]*(long long)i%M;
rev[0]=rev[1]=1;
for (int i=2;
i<=n;
i++)
{
LL x=M/i,y=M%i;
rev[i]=x*x%M*rev[y]%M*rev[y]%M*(long long)i%M;
}
for (int i=2;
i<=n;
i++) rev[i]=rev[i]*rev[i-1]%M;
f[1]=1;
LL sum=1;
for (int i=2;
i<=n;
i++)
{
f[i]=sum*fac[i-2]%M;
f[i]=f[i]*rev[i-1]%M;
sum=(sum+f[i])%M;
if (i-k>=1) sum=(sum-f[i-k]+M)%M;
}
for (int i=1;
i<=n;
i++) ans=(ans+f[i]*fac[n-1]%M)%M;
ans=(fac[n]-ans+M)%M;
printf("%lld\n",ans);
return 0;
} 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 题目|C. Ayoub and Lost Array（思维dp）
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- HDU 5185 Equation (DP)