1006(6038)
就是对a，b分别求循环节，先统计一下b中所有长度循环节的出现次数，再对a求循环节时只要满足： a的循环节长度 % b的循环节长度=0，那么这个b的循环节就可以计入答案，尼玛只要是倍数就可以阿，比赛的时候死命想以为只有长度相同或者b的长度为1才能计算贡献，简直弱智。加了一个for就对了
/** @Date : 2017-07-25 13:22:13
* @FileName: 1006.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL __int64
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8;
const LL mod = 1e9 + 7;
LL a[N];
LL b[N];
bool visa[N];
bool visb[N];
LL cnta[N];
LL cntb[N];
int main()
{
LL n, m;
LL acnt;
int icase = 0;
while(~scanf("%I64d%I64d", &n, &m))
{
MMF(visa);
MMF(visb);
MMF(cnta);
MMF(cntb);
for(int i = 0; i < n; i++)
scanf("%I64d", a + i);
for(int j = 0; j < m; j++)
scanf("%I64d", b + j);
for(int i = 0; i < m; i++)
{
if(!visb[i])
{
visb[i] = 1;
LL np = b[i];
LL c = 1;
while(!visb[np])
{
visb[np] = 1;
np = b[np];
++c;
}
cntb[c]++;
}
}
LL ans = 1;
for(int i = 0; i < n; i++)
{
if(!visa[i])
{
visa[i] = 1;
LL np = a[i];
LL c = 1;
while(!visa[np])
{
visa[np] = 1;
np = a[np];
++c;
}
cnta[c]++;
////
LL tmp = 0;
for(int j = 1; j <= m; j++)
{
if(c % j == 0)
if(cntb[j])
tmp = (tmp + (j * cntb[j]) % mod) % mod;
}
//if(cntb[1] && c != 1)
// tmp = (tmp + cntb[1]) % mod;
//cout << c << " ~"<< c*cntb[c] <<"~" << cntb[1]<< endl;
ans = (ans * tmp + mod) % mod;
}
}
while(ans < 0)
ans+=mod;
printf("Case #%d: %I64d
", ++icase, (ans + mod) % mod);
}
return 0;
}
1012(6044)
给出n个区间$l_i$,$r_i$,要求每个$min{(l_i,r_i)} = p_i$，问能够构成合法情况，且其中的$p_i$大小关系不同的方案有几种。首先我们考虑一个区间$[l_i, r_i]$,如果它的左边界$l_i<i$，那么显然意味着$p_i$左边$i-l_i$个数与右边$r_{i}-i$个数的相对大小是不确定的（因为被$p_i$截断，后续区间的左边界必定不会小于i），而且其后的区间可以不再考虑左边的这些数。那么，我们dfs区间，每次把区间分为两部分$(L, i - 1)$,$(i+1, R)$，其中，一个区间的贡献的情况为$C_{r_{i}-l_{i}}^{i - l_{i}}$，注意判断当前区间是否合法(存在)。这题题目提示还要读入优化的外挂...我不会只能网上找个模板了..
/** @Date : 2017-07-25 16:24:31
* @FileName: 1012 读入优化 组合.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6+20;
const double eps = 1e-8;
const LL mod = 1e9 + 7;
LL inv[N];
LL fac[N];
void init()
{
fac[0] = fac[1] = 1;
inv[0] = inv[1] = 1;
for(int i = 2; i < N; i++)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
for(int i = 1; i < N; i++)
(inv[i] *= inv[i - 1]) %= mod;
}
LL C(LL n, LL k)
{
LL ans = 0;
if(k > n)
return 0;
ans = fac[n] * inv[k] % mod * inv[n - k] % mod;
return ans;
}
struct yuu
{
LL l, r;
yuu(){}
yuu(LL _l, LL _r):l(_l),r(_r){}
bool operator <(const yuu &b) const
{
if(l != b.l)
return l < b.l;
return r < b.r;
}
}a[N];
map<yuu, LL>q;
LL dfs(LL l, LL r)
{
LL ans = 1;
if(l > r)
return 1;
yuu tmp;
tmp.l = l, tmp.r = r;
LL p = q[tmp];
if(p == 0)
return 0;
else if(l == r)
return 1;
ans = ans * C(r - l, p - l) % mod;
LL x = dfs(l, p - 1) % mod;
LL y = dfs(p + 1, r) % mod;
if(!x || !y)
return 0;
ans = (ans * x % mod * y % mod + mod) % mod;
return ans;
}
/////
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int fre(LL &x){
char ch=nc();
if(ch == EOF)
return -1;
x = 0;
while(!(ch>='0'&&ch<='9')) ch=nc();
while(ch>='0'&&ch<='9') x = x*10 + ch - 48, ch = nc();
return 1;
}
/////
int main()
{
init();
int icase = 0;
LL n;
while(/*~scanf("%lld", &n)*/~fre(n))
{
for(int i = 0; i < n; i++)
/*scanf("%lld", &a[i].l);*/ fre(a[i].l);
for(int i = 0; i < n; i++)
/*scanf("%lld", &a[i].r);*/ fre(a[i].r);
q.clear();
for(int i = 0; i < n; i++)
{
q[a[i]] = i + 1;
}
LL ans = dfs(1, n);
printf("Case #%d: %lld
", ++icase, ans);
}
return 0;
}