http://ch.ezoj.tk/contest/CH%20Round%20%2354%20-%20Streaming%20%235%20%28NOIP%E6%A8%A1%E6%8B%9F%E8%B5%9BDay1%29

果然太蒟蒻。t2和t3都是骗分滚粗。。

t2各种逗啊,自己硬是只mod一个不mod两个,,,sad。

t3骗分过程中也是各种逗啊,虽然改骗的良心都骗了orz。。

rp会不会暴跌啊。

另无限orzZYF神犇,千古神犇zyf,只是手抖丢了t1十分,orz。。千古神犇zyf,rank2orzzzzz,290分orzzzzzz

t1:

sb题,只不过注意些细节罢了(表示后边检查的时候发现好多漏洞啊,,,数组开小、‘2’没特判,还好改了过来)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=200005;
char s[N];
int ifind(int n) {
int mx=0, i=1;
while(1) {
if(i>n) break;
int len=0;
if(s[i]=='2') {
len=1;
while(s[++i]=='3') ++len;
mx=max(mx, len);
}
else ++i;
}
return mx;
} int main() {
scanf("%s", s+1);
int n=strlen(s+1);
for1(i, n+1, n+n) s[i]=s[i-n];
int ans=ifind(n);
for1(i, 1, n) if(i>=n-i+1) break; else swap(s[i], s[n-i+1]);
for1(i, n+1, n+n) s[i]=s[i-n];
ans=max(ans, ifind(n));
if(ans==0) puts("TvT");
else {
putchar('2');
rep(i, ans-1) putchar('3');
}
return 0;
}

t2:免农

免(mian)农,233

显然只需要找兔子数是否在某个时刻刚好为modk=1后,后边的情况直接快速幂做掉。

显然偶数直接快速幂做掉。

然后我sb的没有搞好modk=1这里,我没有开两个modk和modMD来搞啊QAQ

注意对p取模一个数和对k取模一个数

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } int n;
typedef long long ll;
ll md, k;
ll mpow(ll a, ll b) {
ll ret=1;
for(; b; b>>=1, a=(a*a)%md) if(b&1) ret=(ret*a)%md;
return ret;
}
int main() {
read(n); read(k); read(md);
if((k&1)==0) { printf("%lld\n", mpow(2, n+1)); return 0; }
ll P=2%k, M=2%md;
for1(i, 1, n) {
P<<=1; M<<=1; P%=k; M%=md;
if(P==1) {
M=((M+md)-1)%md;
M*=mpow(2, n-i);
break;
}
}
printf("%lld\n", M%md);
return 0;
}

t3:高维网络

神题不会做啊。。。看到有部分分且十分良心orz

一维的直接特判有没有p即可。。。

二维的直接普通递推即可(当a>1000后且p==0可以用二项式定理求组合数然后多骗了5分QAQ)

三维的也是直接递推即可(没时间思考组合骗分了。。。。)

65分骗分:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int 4i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 0, b) { for1(__, 0, c) cout << a[_][__] << "\t\t\t\t"; cout << endl << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } typedef unsigned long long ull;
const int M=1001, MD=1000000007, M3=101;
const ull MDD=1000000007;
int d[M][M], n, p, vis[M][M], vis3[M3][M3][M3], d3[M3][M3][M3]; ull mpow(ull a, int b) {
ull ret=1;
for(; b; b>>=1, a=(a*a)%MD) if(b&1) ret=(ret*a)%MD;
return ret;
}
ull getc(ull a, ull b) {
ull up=1, down=1;
for(ull i=b+1; i<=a; ++i) up=(up*i)%MDD;
for(ull i=1; i<=a-b; ++i) down=(down*i)%MDD;
return (up*mpow(down, MDD-2))%MDD;
}
int main() {
read(n); read(p);
if(n==1) {
int flag=0;
for1(i, 1, p) n=getint(), flag=1;
if(flag) puts("0");
else puts("1");
}
else if(n==2) {
int a, b;
read(a); read(b);
if(p==0 && max(a, b)>1000) {
int i=a+b, j=b;
printf("%llu\n", getc(i, j));
return 0;
}
for1(i, 1, p) {
int x=getint(), y=getint();
vis[x][y]=1;
}
d[0][0]=1;
for1(i, 0, a+a) for1(j, 0, b+b) {
if(vis[i][j]) continue;
if(i) d[i][j]+=d[i-1][j];
if(j) d[i][j]+=d[i][j-1];
if(d[i][j]>=MD) d[i][j]%=MD;
}
printf("%d", d[a][b]);
}
else if(n==3) {
int a, b, c;
read(a); read(b); read(c);
for1(i, 1, p) {
int x=getint(), y=getint(), z=getint();
vis3[x][y][z]=1;
}
d3[0][0][0]=1;
for1(i, 0, a) for1(j, 0, b) for1(k, 0, c) {
if(vis3[i][j][k]) continue;
if(i) d3[i][j][k]+=d3[i-1][j][k];
if(j) d3[i][j][k]+=d3[i][j-1][k];
if(d3[i][j][k]>=MD) d3[i][j][k]%=MD;
if(k) d3[i][j][k]+=d3[i][j][k-1];
if(d3[i][j][k]>=MD) d3[i][j][k]%=MD;
}
printf("%d", d3[a][b][c]);
}
else puts("0");
return 0;
}

噗,没想到p=0的时候可以直接排列写啊。。orz zyf

首先到达一个任意点a{a1, a2,...,ad},所需的步数一定是sum{ai},而且在走的过程中,x1+1的步数一定是a1次,所以我们将一个坐标看做一类,然后每一维坐标排列起来就是从0点走向点a的路径,例如

x1x1x2x3的序列就代表到达了点a{2, 1, 1},x1x2x1x3也是同样的到达这个点。

so。。。那么可以知道这是多重排列,总数我就不说了,公式难打。。

这样可以求出p=0的时候的路径数

正解:

由上面的排列可得任意两个点之间的路径数量。

然后可以根据乘法原理和加法原理加加减减了。

ans[i]表示0到i不经过路障的路径数量,那么ans[i]=path[0][i]-sum(path[k][i]*ans[k]),path是两个点之间的无视路障的路径数量

然后用队列搞一下就行了。

这里要注意队列的出入顺序,只有当这个点为终点的边全都走过了才能加入这个点。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int 4i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 0, b) { for1(__, 0, c) cout << a[_][__] << "\t\t\t\t"; cout << endl << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } typedef long long ll;
const int N=505, M=105; ll MD=1000000007;
int m, n, a[N][M], P[10000005], f[N][N], ans[N], q[N], vis[N], front, tail;
ll mpow(ll a, int b) {
ll ret=1;
for(; b; b>>=1, a=(a*a)%MD) if(b&1) ret=(ret*a)%MD;
return ret;
}
inline int mul(ll a, ll b) { return (a*b)%MD; }
bool check(int x, int y) {
for1(i, 1, m) if(a[x][i]>a[y][i]) return 0;
return 1;
}
int dis(int x, int y) {
int up=0, down=1;
for1(i, 1, m) {
int t=a[y][i]-a[x][i];
up+=t;
down=mul(down, P[t]);
}
return mul(P[up], mpow(down, MD-2));
}
int main() {
read(m); read(n);
int sum=0;
for1(i, 1, m) read(a[n+1][i]), sum+=a[n+1][i];
for1(i, 1, n) for1(j, 1, m) read(a[i][j]);
P[0]=1;
for1(i, 1, sum) P[i]=mul(P[i-1], i);
for1(i, 0, n) for1(j, 1, n+1) if(i!=j && check(i, j)) f[i][j]=dis(i, j), vis[j]++;
q[tail++]=0; ans[0]=-1, vis[0]=1;
while(front!=tail) {
int x=q[front++];
for1(y, 1, n+1) if(f[x][y]) {
--vis[y];
ans[y]=(ans[y]-mul(ans[x], f[x][y])+MD)%MD;
if(!vis[y]) q[tail++]=y;
}
}
printf("%d\n", ans[n+1]);
return 0;
}

最新文章

  1. Spring MVC之@RequestBody, @ResponseBody 详解
  2. redis配置文件redis.conf参数说明
  3. [转载]mysql的binlog安全删除
  4. Spring.NET学习
  5. 通过一个表的id同时查询多个表的数据
  6. Linux 下的一个全新的性能测量和调式诊断工具 Systemtap, 第 2 部分: DTrace
  7. 强化学习(六)时序差分在线控制算法SARSA
  8. 通过10046 event来获取真实的执行计划
  9. 【.NET Core项目实战-统一认证平台】第八章 授权篇-IdentityServer4源码分析
  10. C#中类成员的执行顺序
  11. Windows 7 64位安装cURL
  12. HDFS 的垃圾回收配置
  13. react单页面应用的Nginx配置问题
  14. 国内打不开onedrive,怎么办?
  15. itunes connect 改版后无法访问的处理办法
  16. 5分钟了解Mockito
  17. HDU - 4511 小明系列故事――女友的考验(AC自己主动机+DP)
  18. Oracle to_date()函数的用法介绍
  19. 为什么要使用MONO
  20. springMvc上传文件、读取zip/rar文件

热门文章

  1. Expression-Based Access Control
  2. VLC播放RTSP视频延迟问题
  3. npm install 报错:node-pre-gyp ERR! 问题解决
  4. android 蓝牙SPP协议通信
  5. OpenERP|ODOO高德地图应用
  6. C/C++中float和double的存储结构(转)
  7. 13-spring学习-class类型表达式
  8. json servlet通信 显示数据
  9. Linux su命令参数及用法详解--Linux切换用户命令
  10. 阿里云视频服务SDK