闽侯县住房和城乡建设局网站,无锡网站的优化,什么是模板建站,郑州高端网站开发problem
洛谷链接
solution
逆向考虑。ansansans 所有蛋糕中的 aaa 序列出现次数 −-− 在 non−colorfulnon-colorfulnon−colorful 蛋糕中的出现次数。
在所有蛋糕中的出现次数#xff0c;即 (n−m1)⋅kn−m(n-m1)k^{n-m}(n−m1)⋅kn−m#xff0c;枚举 aaa 序列开头的…problem
洛谷链接
solution
逆向考虑。ansansans 所有蛋糕中的 aaa 序列出现次数 −-− 在 non−colorfulnon-colorfulnon−colorful 蛋糕中的出现次数。
在所有蛋糕中的出现次数即 (n−m1)⋅kn−m(n-m1)·k^{n-m}(n−m1)⋅kn−m枚举 aaa 序列开头的位置除去 aaa 序列占据的位置以外的位置的颜色是随便的 1∼k1\sim k1∼k。
因为 aaa 的出现是可以有重复位置的所以每个位置的序列的贡献都是独立计算的没有什么需要去重的问题。
然后考虑在 non−colorfulnon-colorfulnon−colorful 蛋糕中的出现次数。 首先得特判aaa 本身就已经是一个 colorfulcolorfulcolorful 蛋糕。那么只要包含 aaa 就一定是满足条件的蛋糕。 直接输出在所有蛋糕中的出现次数结束程序。 aaa 蛋糕颜色序列中各个颜色互不相同。 考虑用 dpdpdp 来做。 设 f(i,j):f(i,j):f(i,j): 到 iii 为止后面一段连续颜色各不相同的长度为 jjj即 [i−j1,i][i-j1,i][i−j1,i] 颜色互不相同的 non−colorfulnon-colorfulnon−colorful 蛋糕个数。 设计 i−1→ii-1\rightarrow ii−1→i 的转移方程。 随便新选一个未曾出现的颜色。 f(i−1,j−1)⋅(k−j1)→f(i,j):f(i-1,j-1)·(k-j1)\rightarrow f(i,j):f(i−1,j−1)⋅(k−j1)→f(i,j):。 i−1i-1i−1 的长度更长在 iii 时选择了和恰当位置相同颜色将 i−1i-1i−1 恰好卡成了 jjj 的长度。 f(i−1,j′)→f(i,j)j′≥jf(i-1,j)\rightarrow f(i,j)\quad j\ge jf(i−1,j′)→f(i,j)j′≥j。 设 gi,j:g_{i,j}:gi,j: 记录 fi,jf_{i,j}fi,j 类的所有可能蛋糕中出现 a1,...,ma_{1,...,m}a1,...,m 的个数。 事实上我们转移时并不知道具体的蛋糕长相所以不能判断是否连续长度为 mmm 的未重复的就一定是 aaa。 所以在转移时只要 j≥mj\ge mj≥m即出现连续长度达到 mmm 的互不相同颜色的连续蛋糕层就记录贡献。 f(i,j)→g(i,j)f(i,j)\rightarrow g(i,j)f(i,j)→g(i,j)。 因为连续长度有 mmm 的连续蛋糕层的每种情况都是均匀分布最后限制其顺序和颜色值即 /A(k,m)/A(k,m)/A(k,m) 即可。 aaa 蛋糕颜色序列中有重复颜色。 也就是说判断一个蛋糕是否是 colorfulcolorfulcolorful 的区间一定不会横跨 / 完全包含 aaa。 那么 aaa 就将整个蛋糕划分成了前一部分aaa 后一部分三部分彼此独立。 枚举 aaa 的开始位置可以使用卷积 / 乘法定理求左右蛋糕组合情况分开求解进而是一整个蛋糕的颜色序列可能数。 显然求解计算的 non−colorfulnon-colorfulnon−colorful 个数与上面 fff 是一样的转移。 只是在初始化上有所不同。 对 aaa 求前缀和后缀最长不重复颜色长度分别记为 l,rl,rl,r。 用 f(i,j)f(i,j)f(i,j) 来计算前一部分g(i,j)g(i,j)g(i,j) 来计算后一部分这里的 f,gf,gf,g 与上一种情况的 f,gf,gf,g 并不一样。 f0,0f0,1...f0,lg0,0g0,1...g0,r1f_{0,0}f_{0,1}...f_{0,l}g_{0,0}g_{0,1}...g_{0,r}1f0,0f0,1...f0,lg0,0g0,1...g0,r1。 注意这里算的是 non−colorfulnon-colorfulnon−colorful 蛋糕中的贡献所以在 dpdpdp 中不能让连续未重复颜色长度达到 kkk。
code
#include bits/stdc.h
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 25005
#define maxk 405
int n, k, m;
int a[maxn];
int f[maxn][maxk], g[maxn][maxk];
bool vis[maxk];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}bool check( int l, int r ) {memset( vis, 0, sizeof( vis ) );for( int i l;i r;i )if( vis[a[i]] ) return 0;else vis[a[i]] 1;return 1;
}bool colorful() { //判断a是否本身就是彩虹的for( int i 1;i k - 1 m;i )if( check( i, i k - 1 ) ) return 1;return 0;
}signed main() {scanf( %lld %lld %lld, n, k, m );for( int i 1;i m;i ) scanf( %lld, a[i] );int ans ( n - m 1 ) * qkpow( k, n - m ) % mod;if( colorful() ) return ! printf( %lld\n, ans );int l -1, r -1;memset( vis, 0, sizeof( vis ) );for( int i 1;i m;i )if( vis[a[i]] ) { l i - 1; break; }else vis[a[i]] 1;memset( vis, 0, sizeof( vis ) );for( int i m;i 1;i -- )if( vis[a[i]] ) { r m - i; break; }else vis[a[i]] 1;int tot;if( ! ~l ) {f[0][0] 1;for( int i 1;i n;i ) {for( int j 1;j k;j ) {/*因为不能是colorful所以不能让未重复长度达到k1.f[i-1][j-1]-f[i][j] 随便加一个未出现的数字 有(k-j1)种因为f[i-1]是后缀和过的 f[i-1][j-1]-f[i-1][j]f[i-1][j-1]2.f[i-1][jj]-f[i][j] 选择合适位置对应的数字 将未重复长度减小因为f[i-1]是后缀和过的 f[i-1][jj]f[i][j]*/f[i][j] ((f[i - 1][j - 1] - f[i - 1][j] mod) % mod * (k - j 1) % mod f[i - 1][j]) % mod;g[i][j] ((g[i - 1][j - 1] - g[i - 1][j] mod) % mod * (k - j 1) % mod g[i - 1][j]) % mod;if( j m ) ( g[i][j] f[i][j] ) % mod; //当长度达到m的时候就可以计算个数了}for( int j k - 1;j;j -- ) { //后缀和( f[i][j - 1] f[i][j] ) % mod;( g[i][j - 1] g[i][j] ) % mod;}}tot g[n][0]; //此时的g只是算的长度为m的未重复的个数 包含了给出的a 还有一些其余的数列//这里的a强调顺序以及数值 所以要除以A(k,m)for( int i k;i k - m;i -- ) tot tot * qkpow( i, mod - 2 ) % mod;}else {//前后卷积for( int i 0;i l;i ) f[0][i] 1;for( int i 0;i r;i ) g[0][i] 1;for( int i 1;i n;i ) {for( int j 1;j k;j ) {f[i][j] ((f[i - 1][j - 1] - f[i - 1][j] mod) % mod * (k - j 1) % mod f[i - 1][j]) % mod;g[i][j] ((g[i - 1][j - 1] - g[i - 1][j] mod) % mod * (k - j 1) % mod g[i - 1][j]) % mod;}for( int j k - 1;j;j -- ) {( f[i][j - 1] f[i][j] ) % mod;( g[i][j - 1] g[i][j] ) % mod;}}tot 0;for( int i 0;i n - m;i )tot ( tot f[i][0] * g[n - m - i][0] % mod ) % mod;}printf( %lld\n, ( ans - tot mod ) % mod );return 0;
}
