Codeforces Round #525 (Div. 2) C. Ehab and a 2-operation task(数论构造)

思路来源

http://www.cnblogs.com/Dup4/p/10068891.html

题解

注意%可以起到等同于减的作用。

Solution1:

先给区间[1,n]加上一个较大的数D，比如500W，

这样ai就变为D+ai，

由于ai-i<1e5，此时再对[1,i]mod (D+ai-i)时，

D+ai就变为i了，而所mod数D+ai-i大于上一个数i-1，

即(i-1)%(D+ai-i)=i-1

也就是说对[1,i]区间操作时，[1,i-1]不会受到影响。

Solution2:

特判n=1直接输出0 辣鸡就是这么被hack掉的

n>1的情况，

第1次：

先对区间[1,n]加上一个数n，这样最后一个数不会小于n

第2到n-1次：

我们令前n-1个数分别为1，…，n-1即可，

计从后到前的已累加数为lazy，

由于第i个数最后要mod n变为i

故(ai+lazy+b)%n==i，ai+lazy+b==i+kn，

b==i-ai-lazy+kn，即令b=((i-ai-lazy)%n+n)%n，

对当前数加b，然后lazy+=b，

第n次：

对区间[1,n-1]mod n

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int n,a[maxn];
ll pre;
int main()
{ 
   sci(n);
   rep(i,1,n)sci(a[i]);
   if(n==1)puts("0");
   else
   {
   printf("%d\n",n+1);
   printf("%d %d %d\n",1,n,n);//最后一个数大于等于n 
   pre=n;
   for(ll i=n-1;i>=1;--i)
   {
   	ll tmp=pre+a[i],tmp2=((i-tmp)%n+n)%n;
   	printf("%lld %lld %lld\n",(ll)1,i,tmp2);
   	pre+=tmp2;
   }
   printf("%d %d %d\n",2,n-1,n);//前n-1个数mod n  
   }
   return 0;
}