影视评论|《山河故人》非语义世界的荒僻伦理

 
            “玲珑杯”算法比赛 Round #14By:wxh010910

重视词释义:数据的含义就是语义(semantic)。简单的讲,数据就是标志。数据我并未其余意义,唯有被赋予含义的数量才可以被选用,那时候数据就转账为了音讯,而数据的意义就是语义。

 
Start Time:2017-05-13
16:00:00 End
Time:2017-05-13
18:30:00 Refresh
Time:2017-05-20
09:51:24 Public

2000年作为转折点,电影中急剧变动的外部环境,使得社会上出现了两类人,旧世界的人(梁子),新世界的人(晋生),以及在那夹缝中的沈涛。

 

电影中匠心独运的少数也在于把《山河故人》的片名放在了二零一四年始发,似乎经历了一个长达前传,才开首进入了正片,也就是在二〇一四年从前暴发的,都成为了一种经久不衰的亡故,作为一种象征意义存留,成为了过去事件的统称。

 


 玲珑OJ比赛提交地址:http://www.ifrog.cc/acm/contest/1016

先谈谈叶倩文的《爱抚》那首歌。

     
Round#14题解:http://www.ifrog.cc/acm/solution/19 

一首歌分为八个部分,旋律——非语义性的,歌词——语义性的,也就是说歌词赋予旋律含义。

 

《保护》那首歌在电影中的一回出现,都带有非语义性的特点,听歌的人并从未听懂歌词本身的意义,愈来愈多的是对旋律本身的喜好,旋律变成了影片中的线索,串联起了两代人的造化,而旋律的非语义特征也浮现在了人物的性状上来,电影中多少人物的命局特征也多亏这么的无指向性的无目标性的提高。电影中的人物追求的更好的世界,更好的环境,以及更好的启蒙,都是一种符号化的留存,也就是说那种追求不够具体,不负有实际的现实意义,一种想象中的新世界。

A -- No Game No Life


Time Limit:1s Memory Limit:256MByte

多个时刻

梁子,停留在旧世界的人

沈涛,在新旧世界夹缝中的人

晋生,不断前往符号化的新世界。

1999年:新旧交替

1.33:1的画幅

镜头的上马,是在一间舞蹈厅里面,一群洋溢着青春开心的小伙,跳着热情的翩翩起舞,庆贺着就要来临的新世纪,那样的一种的紧凑相连,也结成了对前面剧情的人与人之间的出入的肯定相比较。至少在这么些舞蹈厅的为源点的意况里,大家都是平等和谐。

旧世界里,人们可以紧密的维系在联名,在这一段中有一个极具冲击力的镜头,就是在年会中,满镜头都是人,人挤着人,正是那样的栽培就显得新世界的人情越来越淡漠。

乘胜剧情的深深,此时迪厅出现,迪厅作为新世界的非凡特征,变成了沈涛梁子晋生多少人命局的关口出现,迪厅内迷乱、躁动、狂热,沈涛沉浸在里头,梁子作为旧时代的路人在一旁注视着,此时晋生出现,他看成新世界的代表协作着沈涛,两者在这一阵子交并在了一起。

于是三角关系不同,形成了多少个不一致世界的人。

沈涛接纳了能够满足她对新世界想象的晋生,而梁子就此远离了曾经不复属于她的“故土”。

二零一四年:故土离合

1.85:1画幅

二零一四年第一围绕三段:

沈涛与梁子的重逢

沈涛与三伯的分开

沈涛与外甥的重逢与分离

画面的开首,是负有遗留意味的合影,一群旧时的煤炭工人,最后集结在同步,做着表示离其他合影。

内部意味深长的依然是梁子的地位,依然是煤炭工人,那样符号性的底部百姓特征,从上马到停止,标志性的将其隔离在了新世界之外,而其身患重病,也是其喜剧性命运的抒写。

身患重病的椽子,只得无奈重返家乡。旧时的爱侣相逢,梁子虚弱不堪,而沈涛也将经历生离死别。

在故里沈涛与晋生离婚,沈涛的叔叔在去故人家的中途寿终正寝,张到乐再次回到故里为小叔奔丧。

张到乐一幅新世界的美发登场,在此处道德伦理出现了最大的危机,二姑的角色变成了一个符号性的代表,成为了张到乐不可能接近的存在,而其它一个未曾血缘关系的新世界的亲娘,却更像一个幻象。

从而构起了第三段张到乐的神气世界的弱项。

2024年:远离故土

2.35:1画幅

澳大利Adam做一个符号化的新世界存在,更好的环境,更好的科技(science and technology),更好的启蒙,不过却是一派荒凉的情景。

在澳大基希纳乌,三伯一身旧派的扮相,与事先追求新世界的影象形成巨大的差别,同外甥之间的梗塞也更为大,以至于与外甥的关系要求经过谷歌翻译才能举行下去。

与前边语言作为身份的意味差距的是,在此地语言改为了新旧世界的分界。

MIA与张到乐的爱恋,反倒像是在这么的荒凉的彼岸,相互相互依托,张到乐在MIA身上找到了关联过去的大桥,在与大叔对话中MIA充当那样的翻译工作就见微知着。

最令人高兴的是最后沈涛的出场,偌大的屋宇内,旧地新时情随事迁,一个人一只狗孤独的怀恋人影斑驳的谢世的,真正的把《珍视》里的歌词演绎了出来“纵在两地毕生也等你”。

据此大家由此片引起大家的思索的,导演通过十年的区间,描绘出了多个时辰段,过去,现在,未来,旧有的道德伦理成为“过去”,在“现在”那几个日子段崩坏,而新的德行伦理却并未形成,大家对此“将来”唯有一个符号化的非语义的混淆概念,假诺只是等待十年后,会所有变更的话,那么遗留下来的只是“非语义世界的荒凉”。


七种语言

视频中还有值得观赏的是言语:山西魏语、中文汉语、保加俄克拉荷马城语、巴黎话。

分裂地位之间的互换所利用的言语是见仁见智的,举一个例子,张到乐在二〇一四年与东京后母对话用的就是新加坡话,语言在此间变成了划分身份的存在。

而在第三段中张到乐与岳丈之间的分野,可以说新旧世界的歧异,也是通过言语来拓展。


有关配乐

影片中还有一段相当特殊的钢琴曲,每一遍钢琴曲响起的时候,都是人物关系最为脆弱的时候,那时候响起的钢琴曲就像是一种要断了的弦。

Submissions:473Solved:226

 

DESCRIPTION

一对叫做 的兄妹玩游戏尤其厉害,组队吊打所有人,

不过现实世界对他们很不友好,所以她们就去了异世界,

充裕异世界有16个种族,不可能战斗,只好玩游戏。

有一回他们和数据结构种族的人较量,看何人写数据结构写得快,这时候出现了这么一道题:伦理 1

给一个体系a,每趟四个操作。

1、把拥有数字x变成y2、询问连串一个职位上边的值

INPUT

第一行三个数n,m第二行n个数表示a体系前边有m行,

每行格式为1 x y仍然2
x各自表示把拥有值为x的数变成y或者精通连串上x地方的数值

OUTPUT

对此每个2操作,即摸底,输出一个数表示答案

SAMPLE INPUT

5 55 5 5 5 52 31 5 22 31 8 32 1

SAMPLE OUTPUT

522

HINT

n,m <= 1000, a[i] <= 1000000000你当作四姐自然要AC掉那题啦

SOLUTION

“玲珑杯”ACM比赛 Round #14

标程:

#include <bits/stdc++.h> #define MAXN 100010 using namespace std; int n , m , a[ MAXN ]; map < int , int > wocaonimalegebia; inline int read() { register int x = 0 , ch = getchar(); while( !isdigit( ch ) ) ch = getchar(); while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar(); return x; } int main() { n = read() , m = read(); for( register int i = 1 ; i <= n ; i++ ) a[i] = read() , wocaonimalegebia[ a[i] ] = a[i]; while( m-- ) if( read() == 1 ) { int x = read(); wocaonimalegebia[x] = read(); } else printf( "%d\n" , wocaonimalegebia[ a[ read() ] ] ); return 0; }

B -- RE:从零开首的异世界生活

Time Limit:1s Memory Limit:256MByte

Submissions:368Solved:52

DESCRIPTION

486到了异世界,看到了一群可爱的妹子比如蕾姆啊,艾Milly亚啊,拉姆啊,白鲸啊,怠惰啊之类!
有一天膜女告诉486说她的力量可能不可能再用了,因为膜女在思维一个数据结构题,没情感管486了。
486说自己来帮您做,膜女说您很棒棒哦!
伦理 2

给一个聚众,最开头为空(不是数学上的会晤)
七个操作:

1、插入x
2、把小于x的数变成x
3、把大于x的数变成x
4、求集合中第x小数
5、求集合中小于x的数个数

INPUT

率先行一个数m前面有m行,每行格式为opt
x,opt表示是怎么操作,x表示操作的值

OUTPUT

对于每个4,5操作,输出一个值表示答案

SAMPLE INPUT

51 11 34 12 334 1

SAMPLE OUTPUT

133

HINT

m <= 100000 , x <= 1000000000

SOLUTION

“玲珑杯”ACM比赛 Round #14

 
  标程:

#include <bits/stdc++.h> #define ratio 4 #define MAXN 1000010 #define merge( a , b ) new_Node( a -> size + b -> size , b -> value , a , b ) #define new_Node( s , v , a , b ) ( & ( * st[ cnt++ ] = Node( s , v , a , b ) ) ) #define update( cur ) if( cur -> left -> size ) cur -> size = cur -> left -> size + cur -> right -> size , cur -> value = cur -> right -> value; using namespace std; struct Node { int size , value; Node * left , * right; Node( int s , int v , Node * a , Node * b ) : size( s ) , value( v ) , left( a ) , right( b ) {} Node() {} } * root , * null , * st[300000] , t[300000]; int n , m , x , cnt; int find( int x , Node * cur ) { if( !cur -> left -> size ) return cur -> value; return x > cur -> left -> size ? find( x - cur -> left -> size , cur -> right ) : find( x , cur -> left ); } int zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( int x , Node * cur ) { if( !cur -> left -> size ) return ( x > cur -> value ) * cur -> size; return x > cur -> left -> value ? zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x , cur -> right ) + cur -> left -> size : zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x , cur -> left ); } void split( int x , Node * cur ) { if( x > cur -> left -> size ) split( x - cur -> left -> size , cur -> right ) , cur -> left = merge( cur -> left , cur -> right -> left ) , st[ --cnt ] = cur -> right , cur -> right = cur -> right -> right; else if( x < cur -> left -> size ) split( x , cur -> left ) , cur -> right = merge( cur -> left -> right , cur -> right ) , st[ --cnt ] = cur -> left , cur -> left = cur -> left -> left; } void insert( int x , Node * cur ) { if( !cur -> left -> size ) if( cur -> value < x ) cur -> left = new_Node( cur -> size , cur -> value , null , null ) , cur -> right = new_Node( 1 , x , null , null ); else cur -> left = new_Node( 1 , x , null , null ) , cur -> right = new_Node( cur -> size , cur -> value , null , null ); else insert( x , x > cur -> left -> value ? cur -> right : cur -> left ); update( cur ); } void dispose( Node * cur ) { if( cur -> left -> size ) st[ --cnt ] = cur -> left , st[ --cnt ] = cur -> right , dispose( cur -> left ) , dispose( cur -> right ); } inline void low( int x ) { Node * cur = root; int s = zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x + 1 , cur ); if( s == 0 ); else if( s == cur -> size ) dispose( cur ) , * cur = Node( s , x , null , null ); else split( s , cur ) , dispose( cur -> left ) , * cur -> left = Node( s , x , null , null ); } inline void up( int x ) { Node * cur = root; int s = zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x + 1 , cur ); if( s == 0 ) dispose( cur ) , * cur = Node( cur -> size , x , null , null ); else if( s == cur -> size ); else split( s , cur ) , dispose( cur -> right ) , * cur -> right = Node( cur -> size - s , x , null , null ); } struct io { char ibuf[1 << 23] , * s , obuf[1 << 22] , * t; int a[24]; io() : t( obuf ) { fread( s = ibuf , 1 , 1 << 23 , stdin ); } ~io() { fwrite( obuf , 1 , t - obuf , stdout ); } inline int read() { register int u = 0; while( * s < 48 ) s++; while( * s > 32 ) u = u * 10 + * s++ - 48; return u; } template< class T > inline void print( register T u ) { static int * q = a; if( !u ) * t++ = 48; else { if( u < 0 ) * t++ = 45 , u *= -1; while( u ) * q++ = u % 10 + 48 , u /= 10; while( q != a ) * t++ = * --q; } * t++ = '\n'; } } ip; #define read ip.read #define print ip.print int main() { m = read(); for( register int i = 0 ; i < 300000 ; i++ ) st[i] = & t[i]; null = new_Node( 0 , 0 , 0 , 0 ); while( m-- ) { int opt = read(); if( opt == 1 ) if( root ) insert( read() , root ); else root = new_Node( 1 , read() , null , null ); else if( opt == 2 ) low( read() ); else if( opt == 3 ) up( read() ); else if( opt == 4 ) print( find( read() , root ) ); else print( zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( read() , root ) ); } return 0; }

C -- Another

Time Limit:3s Memory Limit:256MByte

Submissions:230Solved:20

DESCRIPTION

因为意外的由来,主角榊原恒一转学到了夜见山市,进入了3年3班,看到了一个非常可爱的妹子Misaki。
唯独…为啥其余同学都看不见Misaki呢?为何Misaki被号称不存在的人吧?为何班上一贯在尸体呢?
为了搞了解那件事情,主演去学学了OI,准备用图灵测试看看妹子是否AI(正常人不应该困惑妹子是还是不是鬼吗)
在NOIP day1T2,他碰着了一道数据结构题:
伦理 3
给你一个树,每个点有一个颜色,每种颜色有一个值t,定义一个点的奔跑程度ans为:
设子树中颜色为x的点有y个,借使y >= t[x] , ans++;
求所有点的奔跑程度的和

INPUT

先是行三个数n,h,h表示颜色个数前面有n -
1行,每行一个数表示该点的老爹背后有n行,表示每个点的颜色后边有h行,每行表示该颜色的t

OUTPUT

出口一个值表示答案

SAMPLE INPUT

5 512341 2 3 4 511111

SAMPLE OUTPUT

15

HINT

n,m,h,t <=
100000若出现爆栈难题,改栈方法请参见1093标题代码1093地方:http://www.ifrog.cc/acm/problem/1093代码地址:http://ideone.com/Wk24ET

SOLUTION

“玲珑杯”ACM比赛 Round #14

               标程:

                     

#define OPENSTACK #include <bits/stdc++.h> using namespace std; #define MAXN 500010 using namespace std; int n , h , size[ MAXN ] , fa[ MAXN ] , dep[ MAXN ] , son[ MAXN ] , top[ MAXN ] , l[ MAXN ] , r[ MAXN ] , tag[ MAXN ] , tot , p[10000000] , cnt; vector < int > linker[ MAXN ] , wocaonimabi[ MAXN ]; long long ans; inline int read() { int x = 0 , ch = getchar(); while( !isdigit( ch ) ) ch = getchar(); while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar(); return x; } #define cur linker[x][i] void dfs1( int x ) { size[x] = 1; for( int i = 0 ; i < linker[x].size() ; i++ ) if( cur != fa[x] ) { fa[ cur ] = x , dep[ cur ] = dep[x] + 1; dfs1( cur ) , size[x] += size[ cur ]; if( size[ cur ] > size[ son[x] ] ) son[x] = cur; } } void dfs2(int x, int t) { top[x] = t; l[x] = ++tot; if (son[x] ) { dfs2( son[x] , t ); } for( int i = 0 ; i < linker[x].size() ; i++ ) if( cur != fa[x] && cur != son[x] ) dfs2( cur , cur ); } inline void modify( int l , int r ) { tag[l]++ , tag[r + 1]--; p[ ++cnt ] = l , p[ ++cnt ] = r + 1; } void modify( int x ) { while( x ) { modify( l[ top[x] ] , l[x] ); x = fa[ top[x] ]; } } inline void addedge(int x, int y) { linker[x].push_back( y ); } int main() { #ifdef OPENSTACK int size = 128 << 20; // 64MB char *tangtangtangtanglaoshia = (char*)malloc(size) + size; #if (defined _WIN64) or (defined __unix) __asm__("movq %0, %%rsp\n" :: "r"(tangtangtangtanglaoshia)); #else __asm__("movl %0, %%esp\n" :: "r"(tangtangtangtanglaoshia)); #endif #endif n = read() , h = read(); for( int i = 2 ; i <= n ; i++ ) addedge( read() , i ); for( int i = 1 ; i <= n ; i++ ) wocaonimabi[ read() ].push_back( i ); dfs1( 1 ); dfs2( 1 , 1 ); for( int v = 1 ; v <= h ; v++ ) { int t = read(); for(int i = 0 ; i < wocaonimabi[v].size() ; i++ ) modify( wocaonimabi[v][i] ); p[ ++cnt ] = 1 , p[ ++cnt ] = n + 1; sort( p + 1 , p + cnt + 1 ); cnt = unique( p + 1 , p + cnt + 1 ) - p; for(int i = 1 , last = 1 , now = 0 ; i <= cnt ; i++ ) { if( now >= t ) ans += p[i] - last; now += tag[ p[i] ] , tag[ p[i] ] = 0; last = p[i]; } cnt = 0; } cout << ans << endl; #ifdef OPENSTACK exit(0); #else return 0; #endif }

D -- 轻拍翻转小膜女

Time Limit:1s Memory Limit:256MByte

Submissions:36Solved:4

DESCRIPTION

可可娜是一个可爱的初中二年级妹子,本来在认真读书的他偶遇了膜法少女帕比卡,于是和她一同潜入称为pure
illusion的异世界,寻找“mimi的零散”,据说找齐了颇具碎片能够掌控pure
illusion从而掌控世界。
但是…
那番其实讲的是家中伦理…
先不管如此多,有三次可可娜和帕比卡跻身了一个神奇的异世界,里面整套是数据结构题。
他们终于做出了所有题,得到了零散,正准备离开,突然发现距离的谈话上还有最终一道题没被AC,那个题是那般的:
伦理 4

一个体系a,一个操作:
历次询问一个距离,是还是不是存在四个例外数x,y,使得x = y *
z,那里指的是整除!

INPUT

率先行八个数n,m第二行n个数表示a系列后边有m行,每行为l r z表示一个操作

OUTPUT

对于每个操作,输出”flip”表示可以,输出“flap”表示不可以

SAMPLE INPUT

5 51 2 4 8 161 2 22 4 44 5 21 2 82 4 5

SAMPLE OUTPUT

flipflipflipflapflap

HINT

n,m,a[i] <= 1000002 <= z <= 100000

SOLUTION

“玲珑杯”ACM比赛 Round #14

  标程:

       

#include<bits/stdc++.h> #define MAXN 100010 using namespace std; int n , m , block , a[ MAXN ], belong[ MAXN ] , ans[ MAXN ] , cnt[ MAXN ] , last[ MAXN ]; struct ask { int v , l , r , pos; } q[ MAXN ]; vector < ask > linker[MAXN ]; inline bool cmp( const ask& a , const ask & b ) { return belong[ a.l ] ^ belong[ b.l ] ? belong[ a.l ] <belong[ b.l ] : belong[ a.l ] & 1 ? a.r < b.r : a.r > b.r; } inline int read() { register int x = 0 , ch = getchar(); while( !isdigit( ch ) ) ch = getchar(); while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch =getchar(); return x; } int main() { n = read() , m = read(); block = n / sqrt( m / 3 ); for( register int i = 1 ; i <= n ; i++ ) belong[i] = ( i -1 ) / block , a[i] = read(); for( register int i = 1 ; i <= m ; i++ ) q[i].l = read() , q[i].r = read() , q[i].v = read() ,q[i].pos = i; sort( q + 1 , q + m + 1 , cmp ); for( int i = 1 , l = 1 , r = 0 ; i <= m ; i++ ) { while( l > q[i].l ) cnt[ a[ --l ] ]++; while( r < q[i].r ) cnt[ a[ ++r ] ]++; while( l < q[i].l ) cnt[ a[ l++ ] ]--; while( r > q[i].r ) cnt[ a[ r-- ] ]--; if( q[i].v > 300 ) for( register int j = 1 ; j * q[i].v <=100000 && !ans[ q[i].pos ] ; j++ ) if( cnt[j] && cnt[ j * q[i].v] ) ans[ q[i].pos ] = 1; } for( int x = 1 ; x <= 300 ; x++ ) { for( registerint i = 1 ; i <= n ; i++ ) linker[i].clear(); for( register int i = 1 ; i <= m ; i++ ) if( q[i].v == x ) linker[ q[i].l ].push_back( q[i] ); memset( last , 0x3f , sizeof( last ) ); for( register int i = n , j = n + 1 ; i ; i-- ) { if( a[i] * 1ll * x <= 100000 ) j = min( j ,last[ a[i] * 1ll * x ] ); if( a[i] % x == 0 ) j = min( j , last[ a[i] /x ] ); for( register int k = 0 ; k <linker[i].size() ; k++ ) if( linker[i][k].r >= j ) ans[ linker[i][k].pos ] = 1; last[ a[i] ] = i; } } for( register int i = 1 ; i <= m ; i++ ) puts( ans[i] ? "flip" : "flap" ); return 0; } 

E -- 大头日

Time Limit:2s Memory Limit:256MByte

Submissions:69Solved:3

DESCRIPTION

伦理 5
怼大佬是会掉人品的,假设怼成功了,那么rp--,否则rp不变。
有n个大佬,任意多个大佬之间都相互怼了一回,他们之间必有一个怼对方得逞,而另一个告负。
具体来说,那形成了一个竞技图,即随意两点时期有且仅有一条有向边。
每个大佬的开头rp都是0,他们互相怼之后把所有人的rp排序,问有些许种精神分歧的rp连串?

INPUT

一行一个平头表示n。

OUTPUT

一行一个平头表示答案模998244353的值。

SAMPLE INPUT

1

SAMPLE OUTPUT

1

HINT

n <= 100000

SOLUTION

“玲珑杯”ACM比赛 Round #14

   标程:

        

#include <bits/stdc++.h> #define xx first #define yy second #define mp make_pair #define pb push_back #define fill( x, y ) memset( x, y, sizeof x ) #define copy( x, y ) memcpy( x, y, sizeof x ) using namespace std; typedef long long LL; typedef pair < int, int > pa; inline int read() { int sc = 0, f = 1; char ch = getchar(); while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); } while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar(); return sc * f; } const int mod = 998244353; const int MAXN = 262145; inline int qpow(int x, int y, int mod) { int ret = 1; for( ; y ; y >>= 1, x = 1LL * x * x % mod ) if( y & 1 ) ret = 1LL * ret * x % mod; return ret; } namespace NTT { int R[MAXN], n, L, inv; inline void getR() { for( int i = 0 ; i < n ; i++ ) R[ i ] = ( R[ i >> 1 ] >> 1 ) | ( ( i & 1 ) << L - 1 ); inv = qpow( n, mod - 2, mod ); } inline void NTT(int *a, int f) { for( int i = 0 ; i < n ; i++ ) if( i < R[ i ] ) swap( a[ i ], a[ R[ i ] ] ); for( int i = 1, wn = qpow( 3, mod - 1 + f * ( mod - 1 ) / ( i << 1 ), mod ) ; i < n ; i <<= 1, wn = qpow( 3, mod - 1 + f * ( mod - 1 ) / ( i << 1 ), mod ) ) for( int j = 0, w = 1; j < n ; j += i << 1, w = 1 ) for( int k = 0 ; k < i ; k++, w = 1LL * w * wn % mod ) { int x = a[ j + k ], y = 1LL * w * a[ j + k + i ] % mod; a[ j + k ] = ( x + y ) % mod; a[ j + k + i ] = ( x - y + mod ) % mod; } if( f < 0 ) for( int i = 0 ; i < n ; i++ ) a[ i ] = 1LL * a[ i ] * inv % mod; } inline void mul(int *ret, int *a, int *b) { NTT( a, 1 ); NTT( b, 1 ); for( int i = 0 ; i < n ; i++ ) ret[ i ] = 1LL * a[ i ] * b[ i ] % mod; NTT( ret, -1 ); } } inline void inc(int &x, int y) { x += y; if( x >= mod ) x -= mod; } inline void dec(int &x, int y) { x -= y; if( x < 0 ) x += mod; } int n, f[MAXN], g[MAXN], fac[MAXN], inv[MAXN], fnv[MAXN], p[MAXN], p_cnt, phi[MAXN], a[MAXN], b[MAXN], c[MAXN]; inline int C(int x, int y) { return 1LL * fac[ x ] * fnv[ y ] % mod * fnv[ x - y ] % mod; } inline void init() { fac[ 0 ] = inv[ 0 ] = inv[ 1 ] = fnv[ 0 ] = phi[ 1 ] = f[ 0 ] = 1; for( int i = 1 ; i <= ( n << 1 ) ; i++ ) fac[ i ] = 1LL * fac[ i - 1 ] * i % mod; for( int i = 2 ; i <= ( n << 1 ) ; i++ ) inv[ i ] = 1LL * ( mod - mod / i ) * inv[ mod % i ] % mod; for( int i = 1 ; i <= ( n << 1 ) ; i++ ) fnv[ i ] = 1LL * fnv[ i - 1 ] * inv[ i ] % mod; for( int i = 2 ; i <= n ; i++ ) { if( !phi[ i ] ) phi[ p[ ++p_cnt ] = i ] = i - 1; for( int j = 1 ; i * p[ j ] <= n ; j++ ) { if( i % p[ j ] == 0 ) { phi[ i * p[ j ] ] = phi[ i ] * p[ j ]; break; } phi[ i * p[ j ] ] = phi[ i ] * ( p[ j ] - 1 ); } } for( int i = 1 ; i <= n ; i++ ) { int t = C( i << 1, i ); for( int j = i, k = 1 ; j <= n ; j += i, k++ ) if( i & 1 ) dec( g[ j ], 1LL * phi[ k ] * t % mod ); else inc( g[ j ], 1LL * phi[ k ] * t % mod ); if( i & 1 ) g[ i ] = ( mod - g[ i ] ) % mod; g[ i ] = 1LL * g[ i ] * inv[ i << 1 ] % mod; } } inline void solve(int l, int r) { if( l == r ) { f[ l ] = 1LL * f[ l ] * inv[ l ] % mod; return ; } int mid = l + r >> 1; solve( l, mid ); for( NTT::n = 1, NTT::L = 0 ; NTT::n <= r - l + 1 ; NTT::n <<= 1 ) NTT::L++; NTT::getR(); for( int i = 0 ; i < NTT::n ; i++ ) a[ i ] = i + l <= mid ? f[ i + l ] : 0, b[ i ] = ( i + l + 1 ) <= r ? g[ i + 1 ] : 0; NTT::mul( c, a, b ); for( int i = mid + 1 ; i <= r ; i++ ) inc( f[ i ], c[ i - l - 1 ] ); solve( mid + 1, r ); } int main() { n = read(); init(); solve( 0, n ); return printf( "%d\n", f[ n ] ), 0; }

 

相关文章

Comment ()
评论是一种美德,说点什么吧,否则我会恨你的。。。